力扣、牛客例题-----链表_牛客、力扣

例题1 203.移除链表元素

【题目链接】：
移除链表元素
【题目描述】：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

【解题】：
删除所有值为key的节点分为三步：
（1）遍历链表，找到要删除节点cur
（2） 让cur的上一个节点指向cur的下一个节点，删除cur
（3）继续遍历链表，找到所有与key相等的节点，重复（1）（2）步骤，直至遍历完链表

上述过程没有检查头节点，还有要考虑头节点情况，当要删除的数据是第一个节点时，只需要让head指向第二个节点即可做到删除第一个节点

public ListNode removeElements(ListNode head, int key) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

例题2 206.反转链表

【题目链接】：
206.反转链表

【题目描述】：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

【解题】：目的：直接反转链表结构

反转前链表：

反转后链表结构：

实现过程：

先判断链表是否为空，为空直接返回null，从第二个我节点开始逐个使用头插法插入节点，过程如下：

1. 首先使用cur保存head的下一个节点，也就是要插入的节点
2. 将原链表的head节点的next域置为null（反转后成为最后一个节点）
3. 设置head后的节点为cur，使用curNext记录cur的下一个节点
4. 使用头插法将cur插入head的前面（插入成功）
5. head指向cur
6. cur指向curNext
7. 重复（3）（4）（5）（6）步骤，直至cur为null，反转完成
   

public ListNode reverseList(ListNode head) {
		//链表为空
        if(head == null) {
            return null;
        }
        //链表只有一个节点
        if(head.next == null) {
        	return head;
        }
        
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

例题3 876.链表的中间节点

【题目链接】：
876.链表的中间节点

【题目描述】：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

【解题】：
方式一：先求整个链表的长度，再求长度的一半找到中间节点

1. 先求整个链表的长度
2. 再求长度的一半找到中间节点

 public ListNode middleNode(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        int count = size(head) >> 1;
        while (count != 0){
            cur = cur.next;
            count--;
        }
        return cur;
    }
    //求链表的长度
     public int size(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方式二：使用快、慢指针，快指针一次走两步，慢指针一次走一步，当快指针走到终点时，慢指针就刚好停在中间的位置。

public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9

【注意】： while(fast != null && fast.next != null)该条件语句中的两个语句的位置不能颠倒：
如果颠倒之后语句变成 fast.next != null&&fast != null ，当fast为null时，fast.next就会抛出空指针异常。如果没有颠倒时，当fast为null时，第一个条件成立为false，逻辑运算符&& 遵守短路求值的规则，不会对后一个条件进行判断，不会出现异常情况。

例题4 链表中倒数第k个结点

【题目链接】：
链表中倒数第k个结点
【题目描述】：
输入一个链表，输出该链表中倒数第k个结点。

【解题】：
考点：快、慢指针
方式一：

1. 先计算链表的长度len
2. 然后让节点走len-k步得到节点

 public ListNode FindKthToTail(ListNode head,int k) {
        int len = size(head);
        if(k < 0 || head == null || len - k < 0){
            return null;
        }
        
        ListNode cur = head;
        for(int i = 0;i < len - k;i++){
            cur = cur.next;
        }
        return cur;
        
    }
    //求链表的长度
     public int size(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方式二：快、慢指针

1. 快指针fast先走k-1步
2. 快指针fast和慢指针slow同时走
3. 当快指针fast为空时，那么慢指针slow所在的位置就为倒数第k个节点
   原因：快指针fast和慢指针slow之间永远差k-1步，当快指针到达终点，也就是倒数第1的位置时，加上快指针fast和慢指针slow之间k-1步之后，1+（k-1）=k，slow所在的位置就是倒数第k个位置。
   

public ListNode FindKthToTail(ListNode head,int k) {
		//判断k是否小于0   //当链表为空时，直接返回空
        if(k < 0 || head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        
        int count = 0;
        while(count != (k-1)){
         	fast = fast.next;
            if(fast == null){//判断k是否大于链表的长度
                return null;//要找的节点不存在,超过链表的长度
            }
            count++;
        }
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

例题5 21. 合并两个有序链表

【题目链接】：
21. 合并两个有序链表
【题目描述】：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

【解题】：

1. 新建一个虚拟节点
2. 比较head1和head2的大小，谁小放在tempH的后面，串联两个链表的所有节点
3. 如果head1遍历完了，另一个链表head2还没有遍历完只需要temp.next等于head2，串联起来即可
4. 释放虚拟节点，newH = newH.next;
   

 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newH = new ListNode();
        ListNode tmpH = newH;
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val){
                tmpH.next = list1;
                list1 = list1.next;
                tmpH = tmpH.next;
            }else {
                tmpH.next = list2;
                list2 = list2.next;
                tmpH = tmpH.next;
            }
        }
        if(list1 != null) {
            tmpH.next = list1;
        }
        if(list2 != null) {
            tmpH.next = list2;
        }
        newH = newH.next;
        return newH;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

例题6 OR36 链表的回文结构

【题目链接】：
OR36 链表的回文结构
【题目描述】：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

【解题】：
第一步：找到链表的中间位置

第二步：从中间位置开始反转

第三步：从两端开始逐个对比，判断是否是回文

    public boolean chkPalindrome(ListNode head) {
        // write code here
        //找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //反转后半部分的链表
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }


        //判断是否是回文
        while(slow != head && head.next != slow) {
        //当奇数个节点时，slow和head相等，那么就是回文；
        //当偶数个节点时，slow和head的下一个节点相等，那么就是回文；
            if(slow.val != head.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        } 
        return true;
    }
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

例题7 CM11 链表分割

【题目链接】：
CM11 链表分割
【题目描述】：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

【解题】：
题目分析：
首先要将所有小于x的结点排在其余结点之前，那么可以将链表分为两个部分，一部分为小于c的结点数据，一部分为大于等于x的数据，最后将两部分串联起来；并且题目中提到不能改变原来的数据顺序，所以可以使用尾插法来插入数据，可以保证数据的顺序。

该方法分为以下几个步骤：

1. 遍历链表的所有节点，小于x的节点放在be的节点的后面，大于等于x的节点放在ae节点的后面
2. 判断小于x的部分是否为空，如果为空则小于目标值的部分不存在，直接返回后半部分，返回as节点
3. 将两个部分串联起来
4. 如果后半部分存在。需要将后半部分的最后一个元素置为null（要不然会陷入死循环）
   

public ListNode partition(ListNode pHead, int target) {
        if (pHead == null) {
            return null;
        }
        // write code here
        //小于目标值的部分
        ListNode bs = null;
        ListNode be = null;
        //大于等于目标值的部分
        ListNode as = null;
        ListNode ae = null;

        ListNode cur = pHead;
        while (cur != null) {
            ListNode curNext = cur.next;
            if (cur.val < target) {
            // bs为null，插入第一个数据节点
                if (bs == null) {
                    bs = cur;
                    be = cur;
                    cur = curNext;
                } else {
                    be.next = cur;
                    be = cur;
                    cur = curNext;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                    cur = curNext;
                } else {
                    ae.next = cur;
                    ae = cur;
                    cur = curNext;
                }
            }
        }

        //小于目标值的部分不存在
        if (bs == null) {
            return as;
        }
        
        //小于目标值的部分存在
        //将两个部分串联起来
        be.next = as;
        //如果后半部分存在。需要将后半部分的最后一个元素置为null
        if (ae != null) {
            //将最后一个值置为null
            ae.next = null;
        }
        return bs;
    }
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
45
46
47
48
49
50
51
52
53
54

例题8 160.相交链表

【题目链接】：
160.相交链表

【题目描述】：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

【解题】：

在上图中，节点5便是两个链表的相交点，从节点5之后两个链表的后续节点都是相同的，在上图中只需要同时移动head1和head2，只要两个节点相等时，那么就是相交点。这个方法并不完善，如果两个链表的长度不同时，此方法就不可行，如下图：

在上图中的两个链表长度并不相同，我们只需要让长的链表先走上两个链表的差值的步数，再按之前的方法，同时移动head1和head2，只要两个节点相等时，那么就是相交点。
解题步骤如下：

1. 计算两个链表的长度的差值
2. 并让较长的链表先走差值的步数
3. 再让两个链表的节点逐个进行对比
4. 只要相等就是相交点

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = size(headA);
        int len2 = size(headB);
        //计算两个链表的长度的绝对值
        int len = Math.abs(len1 - len2);
        ListNode curA = headA;
        ListNode curB = headB;
        //判断那个链表较长，较长的链表先走差值的步数
        if (len1 > len2) {
            while (len != 0) {
                curA = curA.next;
                len--;
            }
        } else {
            while (len != 0) {
                curB = curB.next;
                len--;
            }
        }
        //两个链表同时走
        while (curA != null && curB != null) {
            //如果存在相等的节点，那么两个链表相交
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        //不存在相交点
        return null;

    }

    //计算链表的长度
    public int size(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
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

如果用 while (hl != hs) 判断是否走到相交点，还需要判断是否走到链表的结尾，如果走到结尾两个节点并没有相遇但是两个值是相等的

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 使用hl和hs分别指向较长的链表，较短的链表
        ListNode hl = headA;
        ListNode hs = headB;
        // 1.获取两个链表的长度
        int len1 = 0;
        while (hl != null) {
            hl = hl.next;
            len1++;
        }
        int len2 = 0;
        while (hs != null) {
            hs = hs.next;
            len2++;
        }
        int len = len1 - len2;
        hl = headA;
        hs = headB;
        if (len < 0) {
            // 改变hl、hs指针的指向
            hl = headB;
            hs = headA;
            len = len2 - len1;
        }
        // 代码截至到此，hl一定指向较长的链表，hs指向较短的链表

        // 2. 让较长的代码先走差值的步数
        while (len != 0) {
            hl = hl.next;
            len--;
        }

        // 3. 两个链表一起走，如果存在节点相等，那么就是相交点
        while (hl != hs) {
            hl = hl.next;
            hs = hs.next;
        }
        // 判断是否走到链表的结尾，如果走到结尾没有相遇但是两个值是相等的
        if (hl == null) { //不相遇
            return null;
        }
        return hl;//相遇点
    }
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
45
46

例题9 141.环形链表

【题目链接】：
141.环形链表
【题目描述】：
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

【解题】：
【思路】 快、慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

再走一步，那么快慢指针就会相遇：

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
• 快指针一次走3步，走4步，…n步行吗？
  
• 无环情况下，快指针会走得快，最快的一定先为空，如果快指针走到结尾null时，那么该链表无环
  

public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){  
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

 public boolean hasCycle(ListNode head) {
        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 == null || fast.next == null) {
            return false;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例题10 142.环形链表||

【题目链接】：
142.环形链表||
【题目描述】：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

【解题】：
【结论】：
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
【证明】

 public ListNode detectCycle(ListNode head) {
        // 获取相遇点
        ListNode node = hasCycle(head);
        //相遇点不存在
        if (node == null) {
            return null;
        }
        //相遇点存在
        ListNode fast = node;
        ListNode slow = head;
        //判断入口点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        //入口点
        return slow;
    }

    public ListNode hasCycle(ListNode head) {
        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 == null || fast.next == null) {
            return null;
        }
        return fast;
    }
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