链表的问题

在这里我主要是总结链表相关的问题和算法，算法题目是leetcode上的题目，每天都会刷，有更新的我的会在这里更新，进行总结。

判断环路问题

快慢指针

力扣141. 环形链表
空间复杂度O(1)，规律是快指针fast每次走两步，慢指针每次走一步。
如果存在环，那么快慢指针最终会相撞。

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

缓存走过的节点

删除链表元素

力扣（203. 移除链表元素）

203. 移除链表元素

递归

使用dfs删除是最方便的。

public class Main{
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) {
            head = removeElements(head.next, val);
        }
        if (head != null) {
            head.next = removeElements(head.next, val);
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

迭代

循环是最优解，需要一个哨兵，保证head后面，包括head都能遍历得到，比如删除下面的1。

public class Main {
    public ListNode removeElements(ListNode head, int val) {
        // 哨兵
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

力扣（83. 删除排序链表的重复元素）

83. 删除排序链表的重复元素

class Solution{
	public ListNode deleteDuplicates(ListNode head) {
        int[] temp = new int[201];
        ListNode t = new ListNode(0);
        t.next = head;
        ListNode c = t;
        while(t.next != null) {
            temp[t.next.val + 100]++;
            if (temp[t.next.val + 100] > 1) {
                t.next = t.next.next;
            } else {
                t= t.next;
            }
        }
        return c.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17