[toc]

Linked List

Overview

  1. Definition: A linked list is a linear data structure consisting of a sequence of elements where each element points to the next element in the sequence.
  2. Types of Linked Lists:
    • Singly Linked List: Each node contains data and a pointer to the next node.
    • Doubly Linked List: Each node contains data, a pointer to the next node, and a pointer to the previous node.
    • Circular Linked List: The last node points back to the first node, forming a circular structure.
  3. In a linked list, the nodes are not stored in contiguous memory locations; instead, they are linked together through pointers. Each node contains data and a pointer to the next node. This non-contiguous distribution allows linked lists to dynamically allocate and deallocate memory during runtime because they do not require a single continuous block of memory. In contrast, arrays need contiguous memory space to store all elements. This distribution makes linked lists more flexible but also results in slower access times since direct indexing is not possible, and traversal from the head is required.链表3
  4. Time Complexity:
    • Insertion/Deletion at the beginning: O(1)
    • Insertion/Deletion at the end (for singly linked list): O(n)
    • Accessing an element: O(n)
  5. Pros and Cons:
    • Pros: Dynamic size, efficient insertion/deletion at the beginning (for singly linked lists), and no need for contiguous memory allocation.
    • Cons: Inefficient random access (no direct access to elements), extra memory overhead for pointers, and traversal requires iteration.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

203. Remove Linked List Elements

Easy

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

img

1
2
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
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
/**
 * 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) {
        if(head == null) return head;
        
        ListNode dummy = new ListNode(-1, head);
        ListNode pointer = dummy;
        
        while(pointer.next != null){
            if(point.next.val == val){
                //if(point.next.next != null){  dont need it
                    point.next = point.next.next;
            }else{
                point = point.next; // notice, need an else statement here, dont put it outside of if statement
            }
            
        }
        return dum.next;
    }
}

✨ dummy node !

707. Design Linked List

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
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val=val;
    }

}
class MyLinkedList {
    int size; //!!!
    ListNode head;
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0); //dummy head!!!!!!!!!!
    }
    
    public int get(int index) {
        if(index >= size || index < 0) return -1;
        ListNode pointer = head;
        // while(index >= 0){
        //     pointer = pointer.next;
        //     index--;
        // }  
        /*i feel like everytime I use while 
        to caculate the times, it goes wrong, 
        so maybe next time just use for iteration*/
        for (int i = 0; i <= index; i++) { // the node on the index !!!!! 
            pointer = pointer.next;
        }
        return pointer.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;
        }
        ListNode pointer = head;
        for (int i = 0; i < index; i++) { // the node before the index !!!!!
            pointer = pointer.next;
        }
        ListNode add = new ListNode(val);
        add.next = pointer.next;
        pointer.next = add;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode pointer = head;
        for (int i = 0; i < index ; i++) { // the node before the index !!!!!
            pointer = pointer.next;
        }
        //if(pointer.next != null){
        pointer.next = pointer.next.next;

        size--;
    }


}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

206. Reverse Linked List

Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

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
/**
 * 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 dummy = new ListNode(-1,head); 这里dummy头不能这样用
        // ListNode left = dummy;
        // ListNode right = dummy.next;
        // ListNode temp = head;
        ListNode left = null;
        ListNode right = head;
        ListNode temp = null;
        while(right != null){
            temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }
        return left;
    }
}

img

24. Swap Nodes in Pairs

Medium

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:

img

1
2
Input: head = [1,2,3,4]
Output: [2,1,4,3]
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
/**
 * 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 dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        ListNode first;
        ListNode second;
        ListNode temp;
        while(cur != null && cur.next != null && cur.next.next != null){
            first = cur.next;
            second = first.next;
            temp = second.next;
            cur.next = second;
            second.next = first;
            first.next = temp;
            cur = first; //!!!!! not second here , attention!!!
        }
        return dummy.next;
    }
}

19. Remove Nth Node From End of List

Medium

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

img

1
2
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
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
/**
 * 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 dummy = new ListNode(-1, head); //!! need dummy head
        if(head == null) return head;
        ListNode right = dummy;
        ListNode left = dummy;
        while(n >= 0){
            right = right.next;
            n--;
        }
        while(right != null){
            left = left.next;
            right = right.next;
        }
        if(left.next != null){ // not left.next.next != null 
            left.next = left.next.next;
        }else{
            left.next = null;
        }
        return dummy.next;
    }
}

finding the intersection of two singly linked lists

https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF

img

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
// (版本一)先行移动长链表实现同步移动
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

}


//(版本二) 合并链表实现同步移动
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// p1 指向 A 链表头结点，p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 链表末尾，转到 B 链表
			if (p1 == null) p1 = headB;
			else            p1 = p1.next;
			// p2 走一步，如果走到 B 链表末尾，转到 A 链表
			if (p2 == null) p2 = headA;
			else            p2 = p2.next;
		}
		return p1;
    }
}

142. Linked List Cycle II

Example 1:

img

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
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.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
         while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
         }
         return null;
    }
}

✨

fast and slow pointers

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

img

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

1
(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y , 为了让后面是加一个数而不是减掉一个数

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。