移除链表元素

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-linked-list-elements/

问题叙述

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

示例 1

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

示例 2

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

示例 3

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

提示

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

分析

创建一个虚拟头结点，从这个头结点的下一个元素挨个判断，如果满足条件则跳过该节点，否则顺序遍历到最后一个元素，最终返回虚拟头结点的下一个节点即可。（因为原头结点可能被删除了）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newhead=new ListNode();
        newhead.next=head;
        ListNode tmp = newhead;
        while (tmp.next != null) {
            if (tmp.next.val == val) {
                tmp.next = tmp.next.next;
            } else
                tmp = tmp.next;
        }
        return newhead.next;
    }
}

设计链表

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-linked-list/

问题叙述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能

  1. get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  2. addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  3. addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  4. addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  5. deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示

所有val值都在 [1, 1000] 之内。
操作次数将在 [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

分析

太基础了，没啥好说的…
注意index是从0开始索引

Code

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
55
56
57
58
59
class LinkList {
    int val;
    LinkList next;

    public LinkList(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    int size;
    LinkList head;

    public MyLinkedList() {
        size = 0;
        head = new LinkList(0);
    }

    public int get(int index) {
        if (index > size || index < 0)
            return -1;
        LinkList tmp = head;
        for (int i = 0; i <= index; i++) {
            tmp = tmp.next;
        }
        return tmp.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        size++;
        LinkList tmp = head;
        LinkList addnum = new LinkList(val);
        for (int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        addnum.next = tmp.next;
        tmp.next = addnum;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index > size) return;
        LinkList tmp = head;
        for (int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        tmp.next = tmp.next.next;
        size--;
    }
}

反转链表

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list/

问题叙述

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

示例 1

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

示例 2

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

示例 3

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

提示

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

分析

双指针 一图懂
双指针反转

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

两两交换链表中的节点

来源：（Leecode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

问题叙述

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

示例 1

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

示例 2

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

示例 3

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

提示

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

分析

递归实现

  1. 返回值：交换完成的子链表
  2. 调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
  3. 终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换

Code

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode next=head.next;
        head.next=swapPairs(next.next);
        next.next=head;
        return next;
    }
}

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

来源:(Leetcode)
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

问题叙述

给你一个链表，删除链表的倒数第 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]

提示

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

进阶

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

分析

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点的下一个节点就可以了。
由于头结点也可能被删除，所以我们创建一个虚拟头结点，让fast和slow初始状态都指向dummy节点，将虚拟头结点的下一个节点作为返回值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (n-- > 0) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

链表相交

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

问题叙述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
相交1
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。

示例 1

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

示例 2

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

示例 3

事例3
输入：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
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶

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

分析

力扣–相交链表题解：我走完我的路，就去走你的路，你走完你的路，再来走我的路，如果我们有缘的话，就会在人生的十字路口相遇，然后一起走完剩下的路，如果我们没机会相遇的话，就在各自的路上当孤勇者吧

Code

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode girl = headA;
        ListNode boy = headB;
        while (boy != girl) {
            girl = girl == null ? headB : girl.next;
            boy = boy == null ? headA : boy.next;
        }
        return boy;
    }
}

环形链表

来源：力扣（Leetcode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/

问题叙述

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

示例 1

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

示例 2

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

示例 3

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

提示

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

进阶

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

分析

  1. 相遇的情况
    设链表共有 a+b 个节点，其中链表头部到链表入口有a个节点（不计链表入口节点），链表环有b个节点，设两指针分别走了f，s步，则有f=2s。而在环内相遇也就是f比s多走了n圈，即f=s+nb，解得f=2nb，s=nb。
    一个指针从头走到环口需要的步数是k=a+nb，而f和s在环内相遇的步数是nb，所以也就是s再走a步，即可到达环口，所以我们在头结点再定义一个指针，当它与s相遇的时候，那个节点就是环口。
  2. 不相遇的情况
    不相遇也就是无环，既fast==null或fast.next==null

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode result = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        while (result != slow) {
            slow = slow.next;
            result = result.next;
        }
        return result;
    }
}