算法笔记-链表结构

链表结构

  • 链表一般采用双指针（快慢指针）或者多个指针进行操作。
  • 在使用过程中要注意通过使用一个dummy哑节点来存储头结点。
  • 最主要要能真正理解指针，指针只是一个引用。
1
2
3
4
5
6
7
ListNode dummy = new ListNode(-1);
dummy.next = head;
....
....
....
return dummy.next

相关题目

反转链表（easy）

解题思路

迭代: 双指针，pre,cur 完善

递归: 递归到尾节点，将其返回，设置下一个节点为

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
class Solution {
    //迭代
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;//指向前一个节点
        ListNode curr = head;//当前节点
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    //递归
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {//递归结束条件返回初始链表最后一个结点
            return head;
        }
        ListNode p = reverseList(head.next);//
        head.next.next = head;//
        head.next = null;//下一个结点
        return p;//始终返回初始链表最后一个结点
    }
}

反转链表II（mid）

解题思路

第一步: 将所指区域进行翻转
第二步: 将翻转和未翻转的链表连接

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        //移动到指定位置
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        //翻转
        for (int i = 0; i < right - left; i++) {
            //翻转
            next = cur.next;
            cur.next = next.next;
            //链接
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}

反转双向链表（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
    // --> --> --> -->
    //1	  2	  3	  4	  5
    // <-- <-- <-- <--
    public ListNode reverse(ListNode head){
        ListNode prev = null,curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            curr.prev = next;//prev
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

环形链表(简单)

题目

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

解题思路

采用哈希表或者快慢指针两中方法

代码实现

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

环形链表 II(中等)

解题思路

先判断是否存在环，再确定其入环节点，采用双指针迭代，步长分别为1和2，当有环时两者会重逢，确定入环节点头节点到环入口的距离=环的长度　　(注意这里的快指针开始结点和慢指针应用，和第一题不同)

官方解题

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;//空值返回
        ListNode slow = head, fast = head;//俩个指针,slow步长1,fast步长2
        while (fast != null) {
            //移动
            slow = slow.next;
            if (fast.next != null) fast = fast.next.next;
            else return null;
            //指针重逢
            if (fast == slow) {//
                ListNode ptr = head;//
                while (ptr != slow) {//当fast和slow重逢时，头节点到环入口的距离=环的长度
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
    
}

环形链表 III（mid）

环形链表求环入口节点，不准使用快慢指针，O(1)空间复杂度，O(n)时间复杂度，可以修改链表节点的指针和数据，不能在链表中新增属性。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution{
    //可以修改链表数据则将其设置一个值，如果遍历工程中有节点的下一个节点是最高值说明其为环入口
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)return null;
        while(head!=null){
            head.val = 10001;
            head = head.next;
            if(head!=null&&head.val==10001)return head;
        }
        return null;
    }
}

相交链表(简单)

解题思路

两条链表分别同时遍历，当到达链尾时指向对方表头再次重逢就是该节点

1
2
3
4
5
6
7
8
9
10
11
12
A:1-2-3-4-5
B:7-8-9-3-4-5

  1-2
	 \
	  3-4-5
	 /
7-9-8

遍历
1-2-3-4-5-7-8-9-`3`
7-8-9-3-4-5-1-2-`3`

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         * 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
         * 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
         **/
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

K个一组翻转链表（hard）

解题思路

代码实现

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
//五个指针变量控制位置
public ListNode reverseKGroup(ListNode head, int k) {
    //辅助指针,表头前一个指针
    ListNode dummy = new ListNode(0);
    //下一个结点指向链表表头
    dummy.next = head;
    //每一组的开头
    ListNode pre = dummy;
    //每一组的结尾
    ListNode end = dummy;

    while (end.next != null) {
        //移动尾部指针
        for (int i = 0; i < k && end != null; i++) end = end.next;
        //尾指针为空直接结束当前循环
        if (end == null) break;
        //开始翻转的指针
        ListNode start = pre.next;
        //下一组的表头
        ListNode next = end.next;
        //将本组末尾元素下一个指针置空
        end.next = null;
        //翻转并返回其表头
        pre.next = reverse(start);
        //链接下一组链表表头
        start.next = next;
        //指向下一组链表表头前一个(这组翻转后的末尾结点)
        pre = start;
        //重置end指针
        end = pre;
    }
    //返回表头
    return dummy.next;
}
//将链表进行翻转
private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

合并两个有序链表(简单)

解题思路

递归或者迭代双指针

代码实现

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
class Solution {
    /**
     * 递归
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /**
     * 迭代
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode prehead = new ListNode(-1);//定义一个头指针
        ListNode prev = prehead;//前一个指针

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

回文链表(简单)

解题思路

1.数组双指针判断

2.递归双指针判断

代码实现

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
60
61
62
63
64
65
class Solution {
    ListNode prev = null;

    //递归
    public boolean isPalindrome(ListNode head) {
        prev = head;
        return helper(head);
    }

    public boolean helper(ListNode head) {
        if (head == null) return true;
        boolean res = helper(head.next);
        if (head.val != prev.val) return false;
        prev = prev.next;
        if (prev == head) return true;
        return res;
    }

    //双指针
    public boolean isPalindrome1(ListNode head) {
        if (head == null) return true;
        List<ListNode> arr = new ArrayList<>();
        while (head != null) {
            arr.add(head);
            head = head.next;
        }
        int i = 0, j = arr.size() - 1;
        while (i < j) {
            if (arr.get(i).val != arr.get(j).val) return false;
            i++;
            j--;
        }
        return true;
    }
    //双指针翻转
    //递归+双指针实现O(1)空间复杂度
    //1.find mid node 使用快慢指针找到链表中点。 2.reverse 逆序后半部分。 3.check 从头、中点，开始比较是否相同。
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head,slow = head;
        //1-2-3-[4]-3-2-1
        //1-2-3-4
        //1-2-[3]-3-2-1
        //1-2-3-3
        //find mid node
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //reverse
        ListNode prev = null,curr = slow;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        //check
        while(prev!=null&&head!=null){
            if(prev.val!=head.val)return false;
            prev = prev.next;
            head = head.next;
        }
        return true;
    }
}

链表中倒数第k个节点(简单)

解题思路

1.两轮循环先获取链表长度，然后循环 长度-k次

2.双指针判断，前指针走k步后，双指针同时向后移动，直到前指针指向链尾部

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;
        for (int i = 0; i < k; i++)
            former = former.next;
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

合并两个链表（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        dummy.next = list1;
        ListNode curr = dummy;
        ListNode aPrev = null;
        for(int i=0;i<=b;i++){
            if(i==a)aPrev = curr;
            curr=curr.next;
        }
        ListNode l2 = list2;
        while(l2.next!=null)l2 = l2.next;
        //拼接
        aPrev.next = list2;
        l2.next = curr.next;
        return dummy.next;
    }
}

合并K个升序链表(困难)

解题思路

分别两组两组合并

代码实现

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
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

LRU 缓存机制(中等)

解题思路

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断 key 是否存在：如果 key 不存在，则返回 −1；如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于 put 操作，首先判断 key 是否存在：如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1)
时间内完成。

小贴士

在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

代码实现

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }
    //添加到头部
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    //移除结点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    //移动到头结点
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    //删除尾部结点
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

复杂度分析

时间复杂度：对于 put 和 get 都是 O(1)。

空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。

LFU 缓存

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
 * Least frequently used
 * 最不经常使用
 *
 * 对每个值进行词频统计，插入超出容量优先删除词频最低的元素
 *
 * 设计：
 * key_table:存储key和node
 * freq_table:存储词频和词频对应的node列表
 *
 * get:更新node的词频，检查是否需要更新minfreq
 * put:检查是否超出容量，超出需要将最小词频的先删除
 */
class LFUCache{
        private int minFreq,capacity;
        Map<Integer,Node> keyMap;
        Map<Integer, LinkedList<Node>> freqMap;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            keyMap = new HashMap<>();
            freqMap = new HashMap<>();
        }
        public int get(int key) {
            if (capacity==0||!keyMap.containsKey(key))return -1;
            Node node = keyMap.get(key);
            //update freq
            int freq = node.freq;
            node.freq=freq+1;
            keyMap.put(key,node);
            //remove old node map
            freqMap.get(freq).remove(node);
            //update minFreq
            if (freqMap.get(freq).size()==0) {
                freqMap.remove(freq);
                if (freq == minFreq) minFreq += 1;
            }
            //update new freq map
            LinkedList<Node> newFreqNodes = freqMap.getOrDefault(freq + 1,new LinkedList<>());
            newFreqNodes.offerFirst(node);
            freqMap.put(freq+1,newFreqNodes);
            return node.val;
        }

        public void put(int key, int value) {
            if (capacity==0)return;
            if (keyMap.containsKey(key)){
                Node node = keyMap.get(key);
                //update node value
                node.val = value;
                int freq = node.freq;
                freqMap.get(freq).remove(node);
                //update minFreq
                if (freqMap.get(freq).size()==0) {
                    freqMap.remove(freq);
                    if (freq == minFreq) minFreq += 1;
                }
                node.freq=freq+1;
                keyMap.put(key,node);
                //update new freq map
                LinkedList<Node> newFreqNodes = freqMap.getOrDefault(freq + 1,new LinkedList<>());
                newFreqNodes.offerFirst(node);
                freqMap.put(freq+1,newFreqNodes);
            }else{//new node
                Node newNoe = new Node(key,value,1);
                if (keyMap.size()==capacity){//need remove least frequently used
                    LinkedList<Node> nodes = freqMap.get(minFreq);
                    Node last = nodes.getLast();
                    nodes.removeLast();
                    if (freqMap.get(minFreq).size()==0){
                        freqMap.remove(minFreq);
                    }
                    keyMap.remove(last.key);
                }
                //direct add
                keyMap.put(key,newNoe);
                minFreq = 1;
                LinkedList<Node> freqNodes = freqMap.getOrDefault(1,new LinkedList<>());
                freqNodes.offerFirst(newNoe);
                freqMap.put(1,freqNodes);
            }
        }
        class Node{
            int key,val,freq;
            public Node(int key, int val, int freq) {
                this.key = key;
                this.val = val;
                this.freq = freq;
            }
        }
    }

重排链表（mid）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
    //线性表
    public void reorderList0(ListNode head) {
        ListNode p = head;
        List<ListNode> list = new ArrayList<>();
        while(p!=null){
            list.add(p);
            p=p.next;
        }
        //reorder
        int left = 0,right = list.size()-1;
        while(left<right){
            list.get(right).next = list.get(left).next;
            list.get(left).next = list.get(right);
            left++;
            right--;
        }
        list.get(left).next = null;
    }
    //寻找链表中点 + 链表逆序 + 合并链表
    public void reorderList(ListNode head) {
        ////寻找链表中点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //链表逆序
        ListNode prev = null,curr = slow.next;
        slow.next = null;//分割前半部分链表
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        //合并prev到head
        while(prev!=null&&head!=null){
            ListNode p_next = prev.next;
            ListNode h_next = head.next;
            head.next = prev;
            prev.next = h_next;
            prev = p_next;
            head = h_next;
        }
    }
}

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }
}

两数相加

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int ans = 0;
        int verb = 0;//进位
        ListNode dummy = new ListNode(-1);
        ListNode ptr = dummy;
        while(l1!=null||l2!=null){
            int v1 = l1==null?0:l1.val;
            int v2 = l2==null?0:l2.val;
            int sum = v1+v2+verb;
            if(sum>=10){
                verb = 1;
                sum = sum - 10;
            }else verb = 0;
            ListNode curr = new ListNode(sum);
            ptr.next = curr;
            ptr = ptr.next;

            l1=l1==null?null:l1.next;
            l2=l2==null?null:l2.next;
        }
        if(verb==1)ptr.next = new ListNode(1);//进位
        return dummy.next;
    }
}

两数相加 II

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
60
61
62
63
64
class Solution {
    //栈方式
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stackL1 = new Stack<>();
        Stack<Integer> stackL2 = new Stack<>();
        while(l1!=null){
            stackL1.push(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            stackL2.push(l2.val);
            l2=l2.next;
        }
        int carry = 0;
        ListNode next = null;
        while(!stackL1.isEmpty()||!stackL2.isEmpty()){
            int rl1v = stackL1.isEmpty()?0:stackL1.pop();
            int rl2v = stackL2.isEmpty()?0:stackL2.pop();
            int sum = rl1v + rl2v + carry;
            carry = sum > 9 ? 1:0;
            sum = sum % 10;
            ListNode newNode = new ListNode(sum);
            newNode.next = next;
            next = newNode;
        }
        if(carry!=0){
            ListNode newNode = new ListNode(carry);
            newNode.next = next;
            next = newNode;
        }
        return next;
    }
    //翻转方式
    public ListNode addTwoNumbersByReverse(ListNode l1, ListNode l2) {
        ListNode rl1 = reverse(l1);
        ListNode rl2 = reverse(l2);
        ListNode curr = new ListNode(-1);
        ListNode ret = curr;
        int carry = 0;
        while(rl1!=null||rl2!=null){
            int rl1v = rl1!=null?rl1.val:0;
            int rl2v = rl2!=null?rl2.val:0;
            int sum = rl1v + rl2v + carry;
            carry = sum > 9 ? 1:0;
            sum = sum % 10;
            curr.next = new ListNode(sum);
            curr = curr.next;
            rl1 = rl1!=null?rl1.next:null;
            rl2 = rl2!=null?rl2.next:null;
        }
        if(carry!=0)curr.next = new ListNode(carry);
        return reverse(ret.next);
    }
    public ListNode reverse(ListNode head){
        ListNode prev = null,curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

链表随机节点

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
//空间换时间
class Solution {
    private List<Integer> list;
    private Random random;
    public Solution(ListNode head) {
        list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        random = new Random();
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}
//蓄水池抽样(时间换空间)
class Solution {
    ListNode head;
    Random random;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    public int getRandom() {
        int i = 1, ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            if (random.nextInt(i) == 0) { // 1/i 的概率选中（替换为答案）
                ans = node.val;
            }
            ++i;
        }
        return ans;
    }
}

删除链表中的节点（easy)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    //后一个补前一个，删掉最后一个
    public void deleteNode(ListNode node) {
        ListNode prev = node;
        while(node.next!=null){
            node.val = node.next.val;
            prev = node;
            node = node.next;
        }
        prev.next = null;
    }
}

移除链表元素（easy）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = dummy;
        while(curr!=null&&curr.next!=null){
            while(curr.next!=null&&curr.next.val==val)curr.next = curr.next.next;
            curr = curr.next;
        }
        return dummy.next;
    }
}

移除重复节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while(head!=null){
            ListNode next = head.next;
            if(!set.contains(head.val)){
                set.add(head.val);
                curr.next = head;
                curr = curr.next;
                curr.next = null;
            }
            head = next;
        }
        return dummy.next;
    }
}

删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;
        while(curr!=null){
            while(curr.next!=null&&curr.val==curr.next.val) curr.next = curr.next.next;
            curr=curr.next;
        }
        return head;
    }
}

删除排序链表中的重复元素 II（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    //三个指针记录prev curr next
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prv = dummy, curr = head,next = head;
        while(next!=null){
            next = next.next;
            if(next!=null&&curr.val==next.val){
                while(next!=null&&next.val==curr.val){
                    next = next.next;
                    if(next!=null&&next.next!=null&&next.next.val==next.val){
                        curr = next;
                        next = next.next;
                    }
                }
                prv.next = next;
                prv = next;
            }else prv = curr;
            curr = next;
        }
        return dummy.next;
    }
}

删除链表的倒数第 N 个结点（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode left = dummy,right = dummy;
        if(left==null)return left;
        for(int i=0;i<n;i++)right = right.next;
        while(right!=null&&right.next!=null){
            left=left.next;
            right=right.next;
        }
        left.next = left.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
36
37
38
39
40
41
class Solution {
		//自己写的垃圾迭代
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode dummy = head.next,p = new ListNode(-1), prev = head,cur = head.next;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev.next = next;
            p.next = cur;
            if(next==null)break;
            p = prev;
            cur = next.next;
            prev = next;
        }
        return dummy;
    }
    //官方的递归
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
    //官方的迭代
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.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
class Solution {
    //思路：复制每个节点插入其每个节点的后面，设置好random在删除旧节点即可
    //剑指offer版本要求恢复原链表指向
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        //复制节点
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        //设置random
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        //移除旧节点
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        return headNew;
    }
}

奇偶链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    //思路：拆分再拼接
    //1->2->3->4->5->6->7->8->9->10
    public ListNode oddEvenList(ListNode head) {
    		if(null==head)return head;
        ListNode odd = head,even = head.next,mid = even;//奇偶节点
        while (odd!=null&&even!=null&&even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = mid;
        return head;
    }
}

旋转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    //思路：双指针
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null||k==0)return head;
        ListNode curr = head, start = null;
        ListNode countPtr = head;
        int count = 0;
        while(countPtr!=null){
            count++;
            countPtr=countPtr.next;
        }
        if(k%count==0)return head;
        int t = k>count ? count - (k%count) -1 : count-k-1;
        for(int i=0;i<t;i++)curr = curr.next;
        start = curr.next;
        curr.next = null;
        ListNode ans = start;
        while(start.next!=null)start = start.next;
        start.next = head;
        return ans;
    }
}

分隔链表（mid)

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
class Solution {
    //思路：双指针(遍历链表查找最后一个小于的节点prev,在prev后查找小于x的节点与之进行交换)
    public ListNode partition(ListNode head, int x) {
        if(head==null)return head;
        ListNode prev = new ListNode(head.val);
        prev.next = head;
        ListNode dummy = prev;
        while(prev!=null&&prev.next!=null&&prev.next.val<x)prev=prev.next;//获取最后一个小于的节点prev
        ListNode curr = prev;
        while(curr!=null&&curr.next!=null&&curr.next.val>x)curr=curr.next;
        while(curr!=null){
            if(curr.next!=null&&curr.next.val<x){//在prev后查找小于x的节点与之进行交换
                ListNode next = curr.next;
                curr.next = next.next;
                ListNode prevNext = prev.next;
                prev.next = next;
                next.next = prevNext;
                prev=prev.next;
            }else  curr = curr.next;
        }
        return dummy.next;
    }
    //
    public ListNode partition(ListNode head, int x) {
        ListNode lmin = new ListNode(-1);
        ListNode lmax = new ListNode(-1);
        ListNode curr = head,minPre = lmin,maxPre = lmax;
        while(curr!=null){
            ListNode next = curr.next;curr.next=null;
            if(curr.val>=x){
                lmax.next = curr;
                lmax = lmax.next;
            }else{
                lmin.next = curr;
                lmin = lmin.next;
            }
            curr = next;
        }
        lmin.next = maxPre.next;
        return minPre.next;
    }
}

排序链表（mid）

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
class Solution {
    //O(nlogn)归并排序
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) return head;
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }
    //合并两个有序链表
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode(-1);
        ListNode ptr = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                ptr.next = l1;
                l1 = l1.next;
            }else{
                ptr.next = l2;
                l2 = l2.next;
            }
            ptr = ptr.next;
        }
        ptr.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

排序奇升偶降链表（mid)

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
class Solution{
    //思路：1.拆分 2.翻转 3.合并两个有序链表
    //1-5-2-4-3-3-4-2
    //1-2-3-4
    //5-4-3-2
    public ListNode sortList(ListNode head){
        ListNode odd = head,even = head.next;
        ListNode down = even;
        while(even!=null){
            ListNode next = even.next;
            odd.next = next;
            odd = odd.next;
            if(odd==null)break;
            even.next = odd.next;
            even = even.next;
        }
        ListNode list = reverse(down);
        return merge(head,list);
    }
    //2.翻转降序的链表
    public ListNode reverse(ListNode head){
        ListNode prev = null,curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    //3.合并
    public ListNode mergeList(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                p.next = l1;l1=l1.next;
            }else{
                p.next = l2;l2=l2.next;
            }
            p = p.next;
        }
        p.next = l1==null?l1:l1;
        return dummy.next;
    }
}

两个链表的第一个公共节点（mid）

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    //遍历到尾部转到另一条链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA,l2 = headB;
        while(l1!=l2){
            l1 = l1 == null ? headB : l1.next;
            l2 = l2 == null ? headA : l2.next;
        }
        return l1;
    }
}

对链表进行插入排序（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    //插入排序:O(n^2)
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        while(head!=null){
            ListNode next = head.next;
            head.next = null;
            insert(dummy,head);
            head = next;
        }
        return dummy.next;
    }
    public void insert(ListNode dummy,ListNode curr){
        while(dummy.next!=null&&dummy.next.val<curr.val)dummy = dummy.next;
        curr.next = dummy.next;
        dummy.next = curr;
    }
}

二进制链表转整数（easy）

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
class Solution {
    public int getDecimalValue(ListNode head) {
        ListNode curNode = head;
        int ans = 0;
        while (curNode != null) {
            ans = ans * 2 + curNode.val;
            curNode = curNode.next;
        }
        return ans;
    }
    public int getDecimalValue0(ListNode head) {
        ListNode prev = null,curr = head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        int ret = 0;
        int bit = 0;
        while(prev!=null){
            ret+=prev.val * Math.pow(2,bit);
            bit++;
            prev = prev.next;
        }
        return ret;
    }
}

设计链表

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class MyLinkedList {
    class Node{
        int val;
        Node prev;
        Node next;
    }
    Node head;
    Node tail;
    public MyLinkedList() {
        head = new Node();
        tail = new Node();
        tail.prev = head;
        head.next = tail;
    }
    public int get(int index) {
        Node node = head;
        for(int i=0;i<=index;i++){
            node = node.next;
            if(node==null||node.next==null)return -1;
        }//print();
        return node.val;
    }
    
    public void addAtHead(int val) {
        Node newNode = new Node();
        newNode.val = val;
        newNode.next = head.next;
        head.next.prev = newNode;
        newNode.prev = head;
        head.next = newNode;//print();
    }
    
    public void addAtTail(int val) {
        Node newNode = new Node();
        newNode.val = val;
        newNode.next = tail;
        newNode.prev = tail.prev;
        tail.prev.next = newNode;
        tail.prev = newNode;
        //print();
    }
    
    public void addAtIndex(int index, int val) {//print();
        if(index<0)addAtHead(val);
        else{
            Node node = head;
            for(int i=0;i<=index;i++){
                node = node.next;
                if(node==null||node.next==null){
                    if(i<index)return;
                    addAtTail(val);return;
                }
            }
            Node newNode = new Node();
            newNode.val = val;
            node.prev.next = newNode;
            newNode.prev = node.prev;
            node.prev = newNode;
            newNode.next = node;
        }
    }
    
    public void deleteAtIndex(int index) {//print();
        Node node = head;
        for(int i=0;i<=index;i++){
            node = node.next;
            if(node==null||node.next==null)return;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    public void print(){
        Node node = head;
        while(node!=null){
            System.out.print(node.val+"--->");
            node = node.next;
        }
        System.out.println();
    }
}

表中的下一个更大节点（mid)

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
class Solution {
    //bf
    public int[] nextLargerNodesBF(ListNode head) {
        List<Integer> list = new LinkedList<>();
        while(head!=null){
            ListNode curr = head.next;
            int max = 0;
            while(curr!=null){
                if(curr.val>head.val){max = curr.val;break;}
                curr = curr.next;
            }
            list.add(max);
            head = head.next;
        }
        int[] ret = new int[list.size()];
        for(int i=0;i<list.size();i++)ret[i]=list.get(i);
        return ret;
    }
    //单调栈
    int count;
    int[] ret;
    Stack<Integer> stack = new Stack<>();
    public int[] nextLargerNodes(ListNode head) {
        if(head==null){
            ret = new int[count];
            return ret;
        }
        count++;
        nextLargerNodes(head.next);
        count--;
        while(!stack.isEmpty()&&stack.peek()<=head.val)stack.pop();
        ret[count] = stack.isEmpty() ? 0 :stack.peek();
        stack.push(head.val);
        return ret;
    }
}

1171. 从链表中删去总和值为零的连续节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        Map<Integer, ListNode> map = new HashMap<>();
        // 首次遍历建立 节点处链表和<->节点 哈希表
        // 若同一和出现多次会覆盖，即记录该sum出现的最后一次节点
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }
        // 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }
        return dummy.next;
    }
}

二叉树中的列表（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        //先判断当前的节点，如果不对，再看左子树和右子树呗
        return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    private boolean isSub(ListNode head, TreeNode node) {
        //特判：链表走完了，返回true
        if (head == null)  return true;
        //特判：链表没走完，树走完了，这肯定不行，返回false
        if (node == null) return false;
        //如果值不同，必定不是啊
        if (head.val != node.val) return false;
        //如果值相同，继续看，左边和右边有一个满足即可
        return isSub(head.next, node.left) || isSub(head.next, node.right);
    }
}

369.

426.

相关资料

基础算法 > 刷题记录
#链表
算法笔记-链表结构
https://mikeygithub.github.io/2019/08/19/yuque/算法笔记-链表结构/
作者
Mikey
发布于
2019年8月19日
许可协议