代码随想录算法训练营day4

代码随想录算法训练营day4 | 链表(2)

一、LeetCode 24 两两交换链表中的节点

题目链接：24.两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/

思路：设置快慢指针，暂存节点逐对进行交换。

代码优化前：

/**
 * 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 swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //头部结点交换
        ListNode cur = head;         //cur存储节点1
        ListNode now = cur.next;    //now存储节点2
        ListNode temp_n = now;       //暂存节点2
        ListNode temp_c = now.next;  //暂存下一轮的节点_1
        now.next = cur;              //节点2 → 节点1
        head = now;                  //head - 节点2
        now = cur;                   //now - 节点1
        cur.next = temp_c;           //节点1 → 节点_1
        cur = temp_c;                //cur - 节点_1
        //while循环中逻辑与上同
        while(cur != null && cur.next != null){
            temp_n = now;
            now = cur.next;
            temp_n.next = now;
            temp_c = now.next;
            now.next = cur;
            now = cur;
            cur.next = temp_c;
            cur = temp_c;
        }
        return head;
    }
}

代码优化后：

二、LeetCode 19 删除链表的倒数第N个节点

题目链接：19.删除链表的倒数第N个节点https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路：考虑使用快慢指针。先处理特殊情况（单节点链表或删除头结点）；快慢指针同时后移、找到要删除节点的前一个节点做删除处理。

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        //单个元素
        if(head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        //删除倒数第n个节点、快指针先行n步
        while(fast != null && n > 0){
            fast = fast.next;
            n--;
        }
        //fast先行n步到链表末尾，说明要删除第一个节点
        if(fast == null){
            return head.next;
        }
        //slow指针与fast指针同时后移，找到要删除节点的前一个节点
        //（所以是fast.next!=null 而不是fast != null）
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        //删除节点
        slow.next = slow.next.next;
        return head;
    }
}

三、LeetCode 面试题 02 07 链表相交

题目链接：面试题02.07.链表相交https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

思路：

计算链表A、B长度、并把指针移动到链表结尾；利用链表A、B长度差，调整较长链表的遍历指针到剩余长度与较短链表的长度相同的位置；A、B遍历指针同步后移，找到相交位置。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode index_a = headA;
        ListNode index_b = headB;
        //处理链表A、B为空的情况
        if(index_a == null || index_b == null){
            return null;
        }
        //计算链表A、B长度、并把指针移动到链表结尾
        int len_a = 1,len_b = 1;
        while(index_a != null && index_a.next != null){
            index_a = index_a.next;
            len_a++;
        }
        while(index_b != null && index_b.next != null){
            index_b = index_b.next;
            len_b++;
        }
        //结尾指针指向的节点不同，说明不相交
        if(index_a != index_b){
            return null;
        }
        //指针回到头部
        index_a = headA;
        index_b = headB;
        //利用链表A、B长度差，调整较长链表的遍历指针到剩余长度与较短链表的长度相同的位置
        //A、B遍历指针同步后移，找到相交位置
        if(len_a > len_b){
            int num = len_a - len_b;
            while(num > 0){
                index_a = index_a.next;
                num--;
            }
            while(index_a != index_b){
                index_a = index_a.next;
                index_b = index_b.next;
            }
        }else{
            int num = len_b - len_a;
            while(num > 0){
                index_b = index_b.next;
                num--;
            }
            while(index_a != index_b){
                index_a = index_a.next;
                index_b = index_b.next;
            }
        }
        return index_a;
    }
}

四、LeetCode 142 环形链表II

题目链接：142.环形链表IIhttps://leetcode.cn/problems/linked-list-cycle-ii/description/

思路：

        先判断是否有环：设置快慢指针fast、slow。在每个循环中，fast后移2次、slow后移1次，作图可知，若链表有环，则fast与slow必然能够相遇且必定在环内相遇。

        再确定环入口：设head到环入口的长度为x，环入口到fast、slow相遇点的长度为y，相遇点到换入口的长度为z，fast在环内转了n圈才遇到slow；又因为fast的移动距离是slow的2倍，则可列： x+y+n*(y+z) = 2*(x+y) → x = (n-1)*(y+z)+z。

        当n = 1时，x = z，设置指针index_1 = head，index_2 = slow/fast(即相遇位置)，易知index_1与index_2以相同的速度后移再相遇的位置即为环入口。

示意图：

代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            //fast指针移速是slow指针的2倍
            fast = fast.next.next;
            slow = slow.next;
            //fast与slow相遇
            if(slow == fast){
                ListNode index_1 = head;
                ListNode index_2 = slow;
                //由思路中的数学分析进行同步后移操作
                while(index_1 != index_2){
                    index_1 = index_1.next;
                    index_2 = index_2.next;
                }
                return index_1;
            }
        }
        //fast最终指向null，链表无环
        return null;
    }
}