LeetCode - Algorithms - 876. Middle of the Linked List

Problem

876. Middle of the Linked List

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while(node!=null) {
            list.add(node);
            node = node.next;
        }
        int n = list.size();
        return list.get(n/2);
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36.3 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode node = head;
        while(node!=null) {
            n++;
            node = node.next;
        }
        node = head;
        n /= 2;
        while(n>0) {
            node = node.next;
            n--;
        }
        return node;
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36.5 MB, less than 11.39% of Java online submissions for Middle of the Linked List.

Two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }
        return slowPointer;
    }
}

Submission Detail

  • 15 / 15 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
  • Memory Usage: 36 MB, less than 9.03% of Java online submissions for Middle of the Linked List.