LeetCodeWeek2

Posted on | In

Prolem876-Submission Detail

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

1
2
3
4
5
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

1
2
3
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

key

题目输出单向链表的中间元素，有这么几个思路

  • O(N)–>遍历放数组，1/2输出return A[t / 2]
  • O(N)–>根据中间特点，mid前进一格，end前进两格

Solution

第一次提交:0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode mid = head;
        ListNode end = head;
        int i=0;
        while(end.next!=null){
            mid = head.next;
            ListNode tmp = mid;
            i++;
            int j=i;
            while(j>0){//搞复杂了
                if(tmp.next==null)return mid;
                end = tmp.next;
                tmp=tmp.next;
                j--;
            }
            head=head.next;
        }
        return mid;
        
    }
}

第二次参考其他代码-提交：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode mid = head, end = head;
        while (mid != null && end.next != null) {
            mid = mid.next;
            end = end.next.next;
        }
        return mid;
    }
}