链表总结

个人看法

既然是总结，那我们就不满足于解出某道题，而是要把我们做过的所有链表题的相关方法和思想都总结一下，看看有没有什么万用的思想或者代码模板，至少要做到遇到新题的时候能有一些思路来做。
实际上我觉得链表的东西更多的就是理解链表指针的移动过程，实在不行也可以画图试试。
牛客的面试必考题还是比较经典的，建议全做，至少要做大半。

知识点

牛客-面试必考真题

1. 双指针：不仅仅有像链表双循环的双指针，这里更多指的是快慢指针算法，常用于判断链表是否有环，找到链表的中间节点，确定链表的倒数第k个节点，找到链表相交的节点，合并两个链表等等。
2. 排序：插入排序，或者分奇偶排序等等。
3. 数学：利用链表做数学知识比如加法什么的
4. 堆：一般出现第K大(小)的时候第一想法就是用堆，java就是用优先队列去做。

模板(建议背下来)

1. 反转链表，可
2. 链表是否有环
3. 链表倒数第k个节点
4. 链表中间节点(也可以引申为1/3节点）
5. 遇到需要更改头节点或者要生成新的链表的题，一定要首先设定哑节点（火车头节点）dummy。

反转链表

双指针

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode curr = head.next;
            head.next = pre;
            pre = head;
            head = curr;
        }
        return pre;
    }
}

附加题可以做做在指定区间反转。

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode curr = head;
        for (int i = 1; i < m; i++){
            pre = curr;
            curr = curr.next;
        }
        for (int i = 0; i < n - m; i++) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.next;
    }
}

链表是否有环

快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            } 
        }
        return false;
    }
}

这个题有一个附加题就是求链表环的入口节点, 可以看看题解什么的手推一下过程。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        return fast;
    }
}

链表倒数第k个节点

双指针，一个指针先走k步就可以了

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = head;
        ListNode slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        } 
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

链表中间节点

slow,fast快慢指针，slow走1步,fast走两步，fast走到链表结尾，slow走到中间节点。1/3节点自然就是fast走3步。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

dummy节点声明

ListNode dummy = new ListNode(-1);
dummy.next = head;

大概能想到的总结的就这么多，之后再想到什么就往文章补。
未完待续...