【leetcode】链表的中间节点

一、题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。
1
2
3

二、解题思路

2.1 暴力解法

• 判断特殊情况：节点数为1的情况
• 遍历链表，将链表节点存入集合(最好使用泛型，能够减少类型转换的开销)，记录链表长度。
• 根据count是单数还是双数来选择访问集合位置，但要注意集合是从0开始存的。

2.2 快慢指针

• 快慢指针不仅仅适用于这一类题，像环形链表、倒数第K个节点等都适用。
• 快慢指针的核心思想就是：两个指针同时走，一个走一步一个走两步，这样快指针走到最后时刻，慢指针恰好指向中间节点。
• 值得注意的是：你需要判断快指针是否为空、快指针的下一个节点是否为空、快指针的下下节点是否为空、以及快指针应该先走几步等等问题
• leetcode快慢指针专题的讲解
• 环形链表题解

三、代码题解

暴力解法：

/**
 * 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 count =1;
        List<ListNode> list =new ArrayList();
        if(head.next==null){
            return head;
        }
        while(true){
            //ListNode head1=head;
            //list中存放的引用直接指向堆内存，而并非是指向head，
            //所以head引用改变,并不会直接改变List集合中存放的元素。
            list.add(head);
            if(head.next!=null){
                head=head.next;
                count++;
                continue;
            }else{
                break;
            }
        }
        if(count%2==0){
            return list.get(count/2);
        }else{
            return list.get(count/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
28
29
30
31
32
33
34
35
36
37

快慢指针：

/**
 * 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 fastHead=head;
        ListNode slowHead=head;
        if(head.next==null){
            return head;
        }else if(head.next.next==null){
            return head.next;
        }
        else{
            while(true){
                slowHead=slowHead.next;
                fastHead=fastHead.next.next;
                if(fastHead.next!=null&&fastHead.next.next==null){
                    return slowHead.next;
                }else if(fastHead.next==null){
                    return slowHead;
                }
            }
        }
    }
}
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
28
29
30
31
32
33