24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、142.环形链表II

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

题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/
文章链接：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频链接：https://www.bilibili.com/video/BV1YT411g7br/

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * cur/dummy->1-2->3-4->null
 */
public class SwapPairs {

    public ListNode swapPairs(ListNode head){

        ListNode dummy = new ListNode();   // 设置一个虚拟头结点
        dummy.next = head;
        ListNode cur = dummy;

        //循环终止条件
        while (cur.next!=null && cur.next.next !=null){    //前者为偶数链表  后者为奇数链表  判断先后顺序不能反
            ListNode temp1 = cur.next;          //存储1节点，防止下面操作断开cur->1的链接无法找打1节点
            ListNode temp2 = cur.next.next.next;    //存储3节点，防止下面操作断开2—>3的链接无法找到3节点

            cur.next = cur.next.next;       //步骤1:cur->2
            cur.next.next = temp1;          //步骤2：2->1
            temp1.next = temp2;             //步骤3:1->3

            cur = cur.next.next;            //移动cur指针，在两量交换节点前一个节点，下一次交换是3—>4节点，cur指针在节点2的位置

        }
        //返回虚拟头结点
        return dummy.next;

    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
文章链接：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
视频链接：https://www.bilibili.com/video/BV1vW4y1U7Gf/

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
 * eg:输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
 */
public class RemoveNthFromEnd {


    public ListNode removeNthFromEnd(ListNode head,int n){
        //定义一个虚拟头结点，在c语言中，是存在带头结点的链表，其次带有数据的第一个节点是首结点
        ListNode dummy = new ListNode();
        dummy.next = head;

        //定义两个快慢指针:指向头结点
        ListNode fastIndex = dummy;     //快指针与慢指针相差n距离
        ListNode slowIndex = dummy;


        //循环结束，快指针移动了n次，与慢指针相差了n距离
        for (int i = 0; i < n; i++) {
            fastIndex = fastIndex.next;
        }

        //此时slowIndex找到待删除元素的前一个位置
        while (fastIndex.next!=null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        slowIndex.next = slowIndex.next.next;
        return dummy.next;

    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

142.环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/
文章链接：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
视频链接：https://www.bilibili.com/video/BV1if4y1d7ob/?vd_source=721f65ae0501389782be0dcb48a2c421

/**
 *  给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 *  tip:
 * 1、判断链表是否环
 * 2、如果有环，找到这个环的入口
 *
 */
public class DetectCycle {

    public ListNode detectCycle(ListNode head){

        //定义虚拟头部节点
        ListNode dummy = new ListNode();
        dummy.next = head;

        //定义快慢指针指向虚拟头结点
        ListNode fastIndex = dummy;
        ListNode slowIndex = dummy;

        //定义快指针的移动是慢指针的两倍，慢指针移动一次，快指针移动两次
        while (fastIndex.next !=null && fastIndex.next.next !=null){
            fastIndex = fastIndex.next.next;
            slowIndex =slowIndex.next;

            //当快指针与慢指针相等的时候，说明有环，他们在环中相遇一次
            if (fastIndex == slowIndex){
                //定义两个指针
                ListNode index1 = fastIndex;  //index1指向环中相遇的位置
                ListNode index2 = dummy;      //index2指向虚拟头结点

                //如果相等的情况说明找到了环的入口
                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                //index1 == index2 都可以返回回去
                return index1;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44