[数据结构与算法][LeetCode]-链表-2

前言

记录LeetCode刷题中遇到的链表相关题目，第二篇

142. 环形链表 II(每日一题)

我们使用快慢双指针来完成这道题。假设链表有环，如上图所示，绿色部分即为环，从链表头head到环入口的距离为a。fast跟slow指针从head出发，fast每次向后移动两个节点，slow每次向后移动一个节点。那么fast跟slow肯定会相遇，假设相遇的节点离环的入口节点距离为b，到环的最后一个节点距离为c。即环的长度为b + c
那么相遇的时候，fast走过的路程为a + n(b + c) + b，n表示fast走过了多少个完整的环，至于n为多大，跟a以及环的长度b + c为多少有关，这不影响我们解题；而slow走过的路程就为a + b，即slow一个完整的环都没走完时，就会与fast相遇。当然，让slow跟fast无休止地走下去的话，它们会相遇很多次，但我们只需要它们第一次相遇的数据就够了，
那么根据fast的“速度”是slow的两倍，就有a + n(b + c) + b = 2(a + b)，化简可得
a = (n - 1)(b + c) + c
等式左边就表示从head到环入口的路程，等式右边可以看成slow把当前走的环剩下的路程c走完后，再走n - 1个环的路程，可以看出来走到最后slow就会在环入口的位置。所以让一个新的指针指向head，然后在head跟slow未相遇时，两个指针都每次向前走一步，直到两个指针相等，所在的节点就是环入口节点

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

234. 回文链表

可以借助反转链表的操作，使用快慢指针找到链表中点，然后将前半部分或后半部分反转，如果把前半部分反转，就比较反转后的前半部分以及原来的后半部分是否相同即可
下面给出的是递归的代码，先找到后半部分的起始节点，然后递归遍历后半部分，递归的效果是后半部分的节点会被逆序访问，而没有直接地去反转链表

class Solution {
    ListNode prv; //prv指向前半部分链表
    boolean rec(ListNode n){
        if(n.next != null){
            if(!rec(n.next)) return false; //如果后面的节点已经出现了不相等的情况则直接返回false
        }
        if(n.val == prv.val){ //否则就比较当前节点跟对应的前半部分中的节点是否相等，同时更新prv
            prv = prv.next;
            return true;
        }
        return false;
    }
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head,slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到后半部分的起始节点，模拟几个例子可以发现，当fast不能继续往前走两步时
        //如果fast此时就是null，那么slow的位置就是后半部分的起始节点
        //不然的话就是fast的next是null，那么slow应该再走一步才是后半部分的起始节点
        if(fast != null) slow = slow.next;
        prv = head;
        return rec(slow);
    }
}

86. 分割链表

快慢双指针：保证慢指针往前的 (包括慢指针本身) 都是小于 x 的节点，慢指针的下一个就是大于等于 x 的节点；由快指针去找到小于 x 的节点，然后将其插入到慢指针的后面。直到快指针指向 null，算法结束
注意点：

1. 为了避免插入到头节点之前的情况，设置一个 dummy 节点作为临时头节点
2. 由于要把快指针的节点插到慢指针之后，那么就要把插入前快指针的前驱节点跟其后继节点相连，由于是单向链表，所以要维护快指针的前驱节点 fastPrv

public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode(-1,head);
    ListNode slow = dummy;
    //让 slow 指向第一个大于等于 x 的节点的之前一个节点
    while(slow.next != null && slow.next.val < x) slow = slow.next;
    ListNode fast = head,fastPrv = dummy;
    //让 fast 指向第一个大于等于 x 的节点
    while(fast != null && fast.val < x){
        fast = fast.next;
        fastPrv = fastPrv.next;
    }
    while(true){
    	//快指针向后查找小于等于 x 的节点
        while(fast != null && fast.val >= x){
            fast = fast.next;
            fastPrv = fastPrv.next;
        }
        if(fast == null) break; //注意及时判断是否遇到 null 及时 break
        //下面就是将fast所指节点插入到slow的后面，同时移动fast 跟 slow
        fastPrv.next = fast.next;
        fast.next = slow.next;
        slow.next = fast;
        slow = slow.next;
        fast = fastPrv.next;
    }
    return dummy.next;
}

61.旋转链表

将链表尾接到链表头上形成循环链表，然后再根据 k 的大小，找到旋转后最后一个节点，将其与其下一个节点的链接断开，断开前先记录最后一个节点的下一个节点，也就是旋转后链表的头节点，断开后返回这个新头节点即可

public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) return head;
        ListNode tmp = head;
        int len = 1;
        //计算链表长度
        while(tmp.next != null){
            tmp = tmp.next;
            len++;
        }
        //如果 k 恰好为链表长度的倍数那就不用旋转 (旋转后跟原来链表是一样的)
        int m = k % len;
        if(m == 0) return head;
        //查找旋转后链表最后一个节点，让tmp指向它
        tmp.next = head;
        m = len - m;
        while(m-- > 0){
            tmp = tmp.next;
        }
        //断开链接
        ListNode res = tmp.next;
        tmp.next = null;
        return res;
    }

2. 两数相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1;
    ListNode p2 = l2;
    ListNode dummy = new ListNode();  //哑节点
    ListNode tmp = dummy;
    int extra = 0;
    while(p1 != null && p2 != null){
        tmp.next = new ListNode();
        tmp = tmp.next;
        int val = p1.val + p2.val + extra;
        extra = val / 10;
        tmp.val = val % 10;
        p1 = p1.next;
        p2 = p2.next;
    }
    while(p1 != null){
        tmp.next = new ListNode();
        tmp = tmp.next;
        int val = p1.val + extra;
        extra = val / 10;
        tmp.val = val % 10;
        p1 = p1.next;
    }
    while(p2 != null){
        tmp.next = new ListNode();
        tmp = tmp.next;
        int val = p2.val + extra;
        extra = val / 10;
        tmp.val = val % 10;
        p2 = p2.next;
    }
    if(extra != 0){
        tmp.next = new ListNode(extra);
        tmp.next.next = null;
    }else {
        tmp.next = null;
    }
    return dummy.next;
}

445. 两数相加 II

跟上面的 链表求和 不一样的地方在于这里的链表从头到尾是从高位到低位，所以利用栈将两个链表中的值反转过来就可以跟 链表求和 一样从低位到高位直接相加了
那怎么做到还是从头到尾只遍历一遍完就得到结果：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
        int count = 0; //用于计算长度
        ListNode head, last;
        for(head = l1; head != null; head = head.next) count++;
        for(head = l2; head != null; head = head.next) count--;
        if(count < 0) {  //让t1指向较长的链。如果count小于0，说明l2更长，那就交换。相加后的值存于l1中
            ListNode t = l1;
            l1 = l2;
            l2 = t;
        } 
        //head用于记录相加后链表的头节点
        //last用于记录 上一个 值小于9 的节点，这样当某一位相加后大于9，就让last节点值增1，
        //然后让last节点与当前节点之间的所有节点 (值都为9) 的值都置为0，完成进位操作
        //在最前面加一个值为0的节点作为初始的last节点，防止最高位也产生进位，如果最终该节点值仍为0则删除该节点
        last = head = new ListNode(0); 
        head.next = l1;  //相加后的值存于l1中
        for(int i = Math.abs(count); i != 0; i--){ //取l1中后面的与l2等长的部分与l2相加
            if(l1.val != 9) last = l1;
            l1 = l1.next;
        }
        int tmp;
        while(l1 != null){
            tmp = l1.val + l2.val;
            if(tmp > 9){                   //发生进位，则更新last到l1之间所有数位的值
                tmp -= 10;
                last.val += 1;
                last = last.next;
                while(last != l1){
                    last.val = 0;
                    last = last.next;
                }
            }
            else if(tmp != 9) last = l1; //没有发生进位且tmp小于9的话，last就应该更新，指向 l1；如果tmp就等于9，那last就保持不变
            l1.val = tmp;
            l1 = l1.next;
            l2 = l2.next;
        }
        return head.val == 1 ? head : head.next; //head等于1说明原来两个链表的最高位发生了进位，返回head
    }

上面的做法应该算是时间上最优解了

剑指 Offer II 023. 两个链表的第一个重合节点

假设有链表A以及链表B，它们重合部分长度为 l，链表A中除了重合部分外前面的部分长度为 l1，链表B中除了重合部分外前面的部分长度为 l2。
让两个指针p1，p2同时开始遍历A和B，且遍历完再去遍历另外一个链表。即对于p1来说，它先去遍历A，遍历完再去遍历B，当遍历B遍历到第一个重合节点时，其走过的路程为 l1 + l + l2；同理对于p2，当它遍历完B再去遍历A且遍历到第一个重合节点时，它走过的路程为 l2 + l + l1，可以发现两个指针走过的路程都是相等的，也就是说它们会在第一个重合节点相遇，所以相遇时直接返回它们所在节点即可

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null) return null;
    ListNode p1 = headA;
    ListNode p2 = headB;
    while(p1 != p2){
        p1 = p1 == null ? headB : p1.next;
        p2 = p2 == null ? headA : p2.next;
    }
    return p1;
}

剑指 Offer 22. 链表中倒数第k个节点(每日一题)

首先想到的做法应该是先遍历一遍链表求出链表的长度 len，然后再从头开始找到第 len - k + 1 个节点就是倒数第 k 个节点
这种做法需要两次遍历 O(n + n)。做单链表的题总要想想能不能只用一次遍历就解决问题，本题的做法就是：既然要找倒数第 k 个节点，如果有两个指针 p1 和 p2，p1 在前 p2 在后，它们距离一直为 k，那么当 p2 指向链表最后面的 null 的时候，p1 指向的不就是倒数第 k 个节点吗。所以先让 p2 走到第 k + 1 个节点的位置，然后再让 p1 从头开始，两个指针每次都一起向后走一步，当 p2 走到 null 的时候，p1 的位置就是倒数第 k 个节点

public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null) return null;
    ListNode p2 = head;
    int endP2 = k + 1; //p2 一开始先走到第 k + 1个节点的位置
    int count = 1; //记录 p2 的位置，一开始在第 1 个节点
    while(p2 != null && count < endP2){
        p2 = p2.next;
        count++;
    }
    if(p2 == null){  //如果循环结束时 p2 就指向 null ，根据count 判断是刚好走到尾还是不够 k 个节点
        if(count == endP2) return head;
        return null;
    }
    //然后让 p1 开始走
    ListNode p1 = head;
    while(p2 != null){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}