203 移除链表元素

题目：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

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

示例 3：

1
2
输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

思路：

题目要求: 删除链表中所有满足 Node.val == val的节点 。

  1. 首先需要删除前缀节点中含有val相等的节点
  2. 接下来就是删除中间和后面含有val相等的节点。

前缀中含有的我们可以直接通过移动头节点到下一个节点即可。

中间的就需要断开要删除的节点的连接， 使其连接到要删除节点的下一位上。 就是node.next = node.next.next

至于末尾的如果有要删除的节点 ，可以直接node = 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
/**
 * 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 removeElements(ListNode head, int val) {
        //先删除头节点
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null) return head;
        //现在得到的头节点一定不会是包含相同val的
        //再删除中间的相同的节点
        ListNode temp = head;
        while(temp.next != null){
            if(temp.next.val == val){
                //这里考虑进去尾节点
                if(temp.next.next == null) {
                    temp.next = null; 
                    return head;
                }
                temp.next = temp.next.next;
            }
            else{
                temp = temp.next; //移动节点 md
            }
        }
        return head;

    }
}

206 翻转链表

题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

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

示例 3：

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

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路

本题有两种解法 ，一种是直接使用双指针来改变节点的指向； 另一种就是使用栈来进行一次进出栈

  1. 使用双指针

首先定义一个虚拟头节点pre， 置为空，然后定义一个nextNode指针， 用于指向当前节点的下一个(为后续移动当前节点做准备)。

接下来就是循环遍历当前节点head, 将当前节点的next指向虚拟头节点， 然后再一步步移动当前节点到之前定义的nextNode的位置， 同时移动虚拟指针pre。

通过上述一步步就可以完成节点指向的转变。

  1. 使用单调栈方式

其实递归本质上就是通过栈的思想实现的， 所以递归的方式也能够完成本题。

首先将所有节点入栈，然后定义一个新的头节点来接收每一个出栈的节点。

实现

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
/**
 * 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 reverseList(ListNode head) {
        ListNode cur; //指向当前指针的下一个
        //制空是因为他最后需要称为尾节点， 尾节点需要为空值
        ListNode pre = null; // 用于改变指针方向
        while(head != null){
            cur = head.next;
            head.next = pre;
            pre = head;
            head = cur;
        }
        return pre;


    /*
      Stack<ListNode> st = new Stack<>();
      ListNode temp = head;
      while(temp!= null){
          st.push(temp);
          temp = temp.next;
      }
      ListNode newHead = new ListNode(0);
      ListNode cur = newHead;
      while(!st.isEmpty()){
          ListNode right = st.pop();
          cur.next = right;
          cur = cur.next;
      }
      //用栈实现需要将最后的指针至空， 不然就是环形

      cur.next = null; 
      return newHead.next;
    */
    }
}

24 两两交换链表中的节点

题目:

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

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

示例 3：

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

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

思路：

这道题本质上和反转链表是一个道理， 都是通过改变节点指针的方向来实现的， 不过本题只需要改变相邻的两个即可。

还是定义一个虚拟头节点， 然后让当前节点指向头节点的下一个节点(也就是首次交换的第二个节点)， 同时还需要将第二个节点反向指向第一个节点， 然后再将第一个节点链接到第三个节点。

整体如图所示 （图片来自《代码随想录》）

image-20231002122944177

实现

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
/**
 * 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 node = new ListNode(0); //虚拟头节点
        node.next = head; //先指向头节点, 将虚拟节点与之前的头节点链接起来 
        ListNode temp = node; 
        ListNode second;
        ListNode third;
        ListNode fourth;
        while(temp.next != null && temp.next.next != null){
            second = temp.next;
            third = temp.next.next; 
            fourth = temp.next.next.next;
            temp.next = third;
            temp.next.next = second;
            temp.next.next.next = fourth;
            //移动指针， 准备交换下一轮
            temp = temp.next.next;
        }
        return node.next;
    }
}

19 删除倒数第n 个节点

题目

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

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

思路

本题实现也是通过双指针，快慢指针。当快指针移动 n 次之后 。 开始移动慢指针。 如果快指针移动到结尾，那么慢指针此时就刚好移动到要删除的节点之前。然后通过node.next = node.next.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
/**
 * 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 temp = head;
        ListNode pre = head;
        for(int i= 0; i< n;i++){
            temp = temp.next;
        }
        if(temp == null) return head.next; //删除的是头节点
        while(temp.next != null){
            temp = temp.next;
            pre = pre.next;
        }
        //删除节点
        pre.next = pre.next.next;
        return head;
    }
}

160 链表相交

题目：

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

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

img

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

img

1
2
3
4
5
6
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

思路

本题当我看到这个图时脑海中才有了思路。

img

这个图是两个链表不相交。 如果两个链表相交的话他们肯定是从某个位置开始结合， 到结尾都是一样的，所以后面的都是一样的， 但是从哪里开始呢 ?

这个没相交的图都是以后端对其的方式比较的，那么我们是不是可以将两个相交的也分开成这样， 然后计算得到每个的长度。 两者相减 就是长的那一方到相交点的距离。

然后移动长的那一个链表到两者距离相同的位置上， 同时开始移动， 找到相等的节点就是题目中需要返回的。 如果没有就直接返回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
45
46
47
/**
 * 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 t1 = headA;
        ListNode t2 = headB;
        int lenA = 0;
        int lenB =0;
        while(t1 != null) {
            t1 = t1.next;
            lenA++;
        }
        while(t2 != null){
            t2 =t2.next;
            lenB++;
        }
        //作为两个节点的差值
        ListNode c1 = headA;
        ListNode c2 = headB;
        if(lenA > lenB){ 
            int cos = lenA - lenB;
            for(int i =0; i < cos; i++) c1 = c1.next;
        }else{
            int cos = lenB - lenA;
            for(int i =0; i < cos; i++) c2 = c2.next;
        }
        //已经将两个节点按照尾部对齐
        while(c1 != null && c2 != null) {
            if(c1 == c2){ 
                return c1;
            }
            c1 = c1.next; 
            c2 = c2.next;
        }
        return null;

    }
}

142 环形链表Ⅱ

题目

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

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

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路

还是快慢指针的思路。快指针一次走两步，慢指针一次一步。 如果两个指针相交 ，那么这个点就是相交点（具体细节这里不解释 ，太麻烦了。 推荐看《代码随想录》）, 然后再定义两个指针一个从头开始遍历， 一个从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
35
36
/**
 * 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 fast = head;
        ListNode slow = head;
        //如果循环结束退出那么就是 null
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                //从头节点到相遇的节点 ，查找步数
                ListNode t1 = fast;
                ListNode t2 = head;
                while(t1 != t2){
                    t1 = t1.next;
                    t2 = t2.next;
                }   
                return t2;
                
            }
        }
        return null;
        
    }
}