代码随想录第四天 链表Part02

语言: Java

参考资料: 代码随想录、ChatGPT3.5

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

力扣题目链接(opens new window)

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

这道题目正常模拟就可以了。

建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

对虚拟头结点的操作，还不熟悉的话，可以看这篇链表：听说用虚拟头节点会方便很多？ (opens new window)。

接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序

初始时，cur指向虚拟头结点，然后进行如下三步：

		   cur.next.next.next = tmp1;
            cur.next.next = tmp3;
            cur.next = tmp2;

完整代码:

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

19.删除链表的倒数第N个节点

力扣题目链接(opens new window)

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

进阶：你能尝试使用一趟扫描实现吗？

输入：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个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

思路是这样的，但要注意一些细节。

分为如下几步：

• 首先这里我推荐大家使用虚拟头结点，这样方便处理删除实际头结点的逻辑，如果虚拟头结点不清楚，可以看这篇： 链表：听说用虚拟头节点会方便很多？(opens new window)
• 定义fast指针和slow指针，初始值为虚拟头结点
• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
• fast和slow同时移动，直到fast指向末尾
• 删除slow指向的下一个节点

代码:

/**
 * 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 dummyhead = new ListNode();
        dummyhead.next = head;
        ListNode fast = dummyhead;
        ListNode slow = dummyhead;
        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 dummyhead.next;
    }
}

面试题 02.07. 链表相交

同：160.链表相交

力扣题目链接(opens new window)

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

思路

简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

/**
 * 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 lengthA = 0;
        ListNode i = headA;
        while (i != null) {
            lengthA++;
            i = i.next;
        }
        int lengthB = 0;
        ListNode j = headB;
        while (j != null) {
            lengthB++;
            j = j.next;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        // curA遍历长的链表
        // lengthA是长的链表的长度
        if(lengthB > lengthA) {
            ListNode tmpnode;
            tmpnode = curA;
            curA = curB;
            curB = tmpnode;
            int tmpint;
            tmpint = lengthA;
            lengthA = lengthB;
            lengthB = tmpint;
        }
        int dis = lengthA - lengthB;
        while(dis > 0) {
            curA = curA.next;
            dis--;
        }
        while(curA != null) {
            if(curA == curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

142.环形链表II

力扣题目链接(opens new window)

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

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

思路

建议看视频: 《代码随想录》算法视频公开课 (opens new window)：把环形链表讲清楚！| LeetCode:142.环形链表II (opens new window)，

代码:

/**
 * 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) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if (fast != slow) {
            return null;
        }
        
        ListNode index1 = slow;
        ListNode index2 = head;
        while (index1 != index2) {
            index1 = index1.next;
            index2 = index2.next;
        }
        return index1;
    }
}