代码随想录算法训练营第三天|24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II、总结

24. 两个交换链表中的节点

扣除主题链接(opens new window)

给定链表，两两交换相邻节点，并返回交换链表。

您不能只是简单地改变节点的内部值，而是需要实际的节点交换。

思路：

按上述顺序记录，防止某个节点意外失踪。

/** * 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 dummy = new ListNode(-1, head);        ListNode cur = dummy;        while(cur.next != null && cur.next.next != null){            ListNode tmp = cur.next;            ListNode tmp1 = cur.next.next.next;            cur.next = cur.next.next;            cur.next.next = tmp;            cur.next.next.next = tmp1;            cur = cur.next.next;        }        return dummy.next;    }}

扣除主题链接(opens new window)

给你一个链表，删除链表倒数第 n 结点，并返回链表的头结点。

高级:你能试着用扫描来实现吗？

示例 1：

输入：head = [1，2，3，4，5]， n = 2 输出：[1，2，3，5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

思路：

双指针方法，最终删除的节点，必须知道它的前一个节点才能删除。n可以转换为两个指针之前的距离。

/** * 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) {        ListNode dummy = new ListNode(-1,head);        ListNode pre = dummy;        ListNode cur = head;        for(int i = 0; i < n; i++){            cur = cur.next;        }        while(cur != null){            pre = pre.next;            cur = cur.next;        }        pre.next = pre.next.next;        return dummy.next;    }}

同样:160.链表相交

扣除主题链接(opens new window)

给你两个单链表的头节点headad 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，请返回 null 。

节点中显示了两个链表 c1 开始相交：

题目数据 保证 环不存在于整个链结构中。

请注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

示例 2：

示例 3：

思路：

一开始的想法真的不是很好。想了十分钟，看了眼题解的开头。要知道是否有相交节点，需要先抹去两个链表的长度差，长指针和短指针保持相同的位置。如果节点仍然不一致，请向下搜索heada == 要注意headB的情况，如果找到了最后，headA == null和headB == null找不到headall == headB的情况表明两者之间没有相交的节点。

/** * 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) {        int lenA = 0;        int lenB = 0;        ListNode cura = headA;        ListNode curb = headB;        while(cura != null){            lenA++;            cura = cura.next;        }        while(curb != null){            lenB++;            curb = curb.next;        }        if(lenA > lenB){            int n = lenA-lenB;            while(n-- > 0){                headA = headA.next;            }            while(headA != headB && headA != headB && headA != null && headB != null){                headA = headA.next;                headB = headB.next;            }            if(headA != null){                return headA;            }            return null;        }else{            int n = lenB-lenA;            while(n-- > 0){                headB = headB.next;            }            while(headA != headB && headA != headB && headA != null && headB != null){                headA = headA.next;                headB = headB.next;            }            if(headA != null){                return headA;            }            return null;        }    }}

扣除主题链接(opens new window)

题意： 给定链表，返回链表开始进入环的第一个节点。 如果链表无环，则返回 null。

使用整数来表示给定链表中的环 pos 表示链表尾连接到链表的位置(索引从 0 开始）。 如果 pos 是 -1.链表中没有环。

注：不允许修改给定的链表。

思路：

刷完这个问题，想了很久，需要运用一定的数学思维，无法理解或者无法理解。第二刷只想用快慢指针来判断是否有环。慢指针一次移动一步，快指针一次移动两步。如果快指针没有null，最终slow等于fast，说明会有环。

找到判断环后，我去计算入口节点时出现了问题。我错误地认为快速和慢指针遇到的节点是环的入口，导致计算加班。在阅读了问题解决方案后，我发现计算环入口节点是亮点。

如图所示，x表示从开始到入口的距离，z表示从入口到快速和慢指针相遇的节点，y表示相遇节点到入口的距离。因此，有以下关系：

slow移动 （x+z）， fast 移动 x+z+n(y+z)，以及 2(x+z) = x+z+n(y+z) => x = (n-1)(y+z)+y ， n表示fast指针在环内的圈数，如果n-1的环内距离被抵消，就可以推断出x = y，同时放两个指针出发。相遇的地方是入口

/** * 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){            slow = slow.next;            fast = fast.next.next;            if(slow == fast){    //确定有环                ListNode index1 = head;                ListNode index2 = fast;                while(index1 != index2){                    index1 = index1.next;                    index2 = index2.next;                }                return index1;            }        }        return null;    }}

总结：

双指针和虚拟头节点是最重要的方法。理清链表之间的联系可以解决很多问题。比起直接刷AC的问题，我还是很欣慰的，这是一个明显的进步。