Made by Mike_Zhang
数据结构与算法主题：
Linked List is a linear data structure, with separate object in it. Each object is linked together by the reference field.
Singly Linked List:
Doubly Linked List:
1 Singly Linked List
1.2 Introduction
Singly Linked List contains it value and the reference field pointing to its next node.
Node Structure of a Singly Linked List:
1
2
3
4
5
| public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode(int x) { val = x; }
}
|
Implementation of the Linked List (Singly and Doubly):
Design Linked List
LeetCode Problem #707
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| class MyLinkedList {
private Node head;
private int len;
public MyLinkedList() {
head = new Node();
len = 0;
}
public int get(int index) {
if ((len == 0) || (index >= len) || index < 0) {return -1;}
if (index == 0) {return head.getVal();}
int out = 0;
Node n = head;
while (out != index){
n = n.getNext();
out+=1;
}
return n.getVal();
}
public void addAtHead(int val) {
Node newHead = new Node(val);
if (len == 0) {
head = newHead;
}
else{
newHead.setNext(head);
head.setPrev(newHead);
head = newHead;
}
len+=1;
}
public void addAtTail(int val) {
Node newTail = new Node(val);
if (len == 0) {
head = newTail;
}
else{
Node n = head;
while (n.getNext() != null) {
n = n.getNext();
}
n.setNext(newTail);
newTail.setPrev(n);
}
len+=1;
}
public void addAtIndex(int index, int val) {
if (index == 0) {
addAtHead(val);
}
else if (index == len) {
addAtTail(val);
}
else if (index > 0 && index <len) {
int i = 0;
Node n = head;
Node newOne = new Node(val);
while (i != index-1) {
n = n.getNext();
i+=1;
}
Node oriNext = n.getNext();
newOne.setNext(oriNext);
oriNext.setPrev(newOne);
n.setNext(newOne);
newOne.setPrev(n);
len+=1;
}
}
public void deleteAtIndex(int index) {
if (index>=0 && index<len) {
if (index == 0) {
head = head.getNext();
}
else {
int i = 0;
Node n = head;
while (i != index-1) {
n = n.getNext();
i+=1;
}
n.setNext((n.getNext()).getNext());
if (n.getNext()!=null) {
(n.getNext()).setPrev(n);
}
}
len-=1;
}
}
}
class Node {
private int val;
private Node next;
private Node prev;
public Node() {
next = null;
prev = null;
}
public Node(int inVal) {
val = inVal;
next = null;
prev = null;
}
public int getVal() {
return val;
}
public Node getNext() {
return next;
}
public void setNext(Node newNext) {
next = newNext;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node newPrev) {
prev = newPrev;
}
}
|
1.3 Two-Pointer Technique
Principle:
- Slow pointer: move forward one step pre loop;
- Fast pointer: move forward two step pre loop;
If the Linked List has a cycle:
- the fast pointer will eventually meet the slow one;
If the Linked List has NO cycle:
- the fast pointer will reach the end of the Linked List;
Linked List Cycle
LeetCode Problem #141
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next == null) { return false;}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
|
Linked List Cycle II
LeetCode Problem #142
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null || head.next == null) { return null;}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
slow = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
|
Intersection of Two Linked Lists
LeetCode Problem #160
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
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode hA = headA;
ListNode hB = headB;
while (hA != null) {
hA = hA.next;
lenA += 1;
}
while (hB != null) {
hB = hB.next;
lenB += 1;
}
int lenAbs = Math.abs(lenA-lenB);
if (lenA > lenB) {
while (lenA != lenB) {
headA = headA.next;
lenA -= 1;
}
}
if (lenA < lenB) {
while (lenA != lenB) {
headB = headB.next;
lenB -= 1;
}
}
while (headA != null || headB != null) {
if (headA == headB) {
return headA;
}
else {
headA = headA.next;
headB = headB.next;
}
}
return null;
}
}
|
Remove Nth Node From End of List
LeetCode Problem #19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
for (int i = 0;i<n;i++) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
|
1.4 Classic Problems
Reverse Linked List
LeetCode Problem #206
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode h = head;
while (head != null && head.next != null) {
ListNode newH = head.next;
head.next = head.next.next;
newH.next = h;
h = newH;
}
return h;
}
}
|
Remove Linked List Elements
LeetCode Problem #203
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {return head;}
while (head != null && head.val == val) {head = head.next;}
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.next.val == val) {
curr.next = curr.next.next;
}
else {
curr = curr.next;
}
}
return head;
}
}
|
Odd Even Linked List
LeetCode Problem #328
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
ListNode curr = head;
ListNode oddHead = head.next;
while (curr.next != null && curr.next.next != null) {
ListNode nextCurr = curr.next.next;
curr.next.next = curr.next.next.next;
curr.next = nextCurr;
curr = curr.next;
}
curr.next = oddHead;
return head;
}
}
|
Palindrome Linked List
LeetCode Problem #234
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
private ListNode h;
private boolean recursivelyCheck(ListNode curr) {
if (curr != null) {
if (!(recursivelyCheck(curr.next))) {return false;}
if (curr.val != h.val) {return false;}
h = h.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
h = head;
return recursivelyCheck(head);
}
}
|
Merge Two Sorted Lists
LeetCode Problem #21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode outHead = new ListNode();
ListNode cur = outHead;
while(list1 != null && list2 !=null) {
if (list1.val < list2.val) {
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}
else {
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
cur.next = list1 != null? list1:list2;
return outHead.next;
}
}
|
Add Two Numbers
LeetCode Problem #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
| class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode out = new ListNode();
ListNode outH = out;
ListNode h1 = l1;
ListNode h2 = l2;
int curr = 0;
int c = 0;
while (h1 != null && h2 != null) {
curr = h1.val+h2.val+c;
out.val = curr % 10;
c = curr / 10;
h1 = h1.next;
h2 = h2.next;
if (h1 != null || h2 != null) {
out.next = new ListNode();
out = out.next;
}
}
while (h1 != null) {
curr = h1.val+c;
out.val = curr % 10;
c = curr / 10;
h1 = h1.next;
if (h1 != null) {
out.next = new ListNode();
out = out.next;
}
}
while (h2 != null) {
curr = h2.val+c;
out.val = curr % 10;
c = curr / 10;
h2 = h2.next;
if (h2 != null) {
out.next = new ListNode();
out = out.next;
}
}
if (c != 0) {
out.next = new ListNode(c);
}
return outH;
}
}
|
Rotate List
LeetCode Problem #61
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
| class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {return head;}
int l = 0;
ListNode curr = head;
while (curr != null) {
l += 1;
curr = curr.next;
}
k = k % l;
if (k == 0) {return head;}
ListNode fast = head;
ListNode slow = head;
while (k > 0){
fast = fast.next;
k-=1;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
}
}
|
Remove Duplicates from Sorted List
LeetCode Problem #83
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode curr = head;
while (curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;
}
else {curr = curr.next;}
}
return head;
}
}
|
Remove Duplicates from Sorted List II
LeetCode Problem #82
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode hp = new ListNode(0,head);
ListNode curr = hp;
while (head != null) {
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
curr.next = head.next;
}
else {
curr = curr.next;
}
head = head.next;
}
return hp.next;
}
}
|
Middle of the Linked List
LeetCode Problem #876
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public ListNode middleNode(ListNode head) {
if (head.next == null) {return head;}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
|
Swap Nodes in Pairs
LeetCode Problem #24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
}
|
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
| class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {return head;}
ListNode sentinal = new ListNode(0,head);
ListNode old = head;
ListNode newHead = head.next;
ListNode nextNew = newHead.next;
boolean flag = true;
ListNode out = new ListNode();
while (old!=null && old.next!=null) {
sentinal.next = newHead;
newHead.next = old;
old.next = nextNew;
if (flag) {
out = newHead;
flag = false;
}
sentinal = old;
old = nextNew;
if(nextNew != null && nextNew.next != null) {
newHead = nextNew.next;
nextNew = newHead.next;
}
}
return out;
}
}
|
2022-10-04
Last updated on 2022-11-25
References
Linked List - Explore - LeetCode
写在最后
Linked List相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！
原创文章，转载请标明出处
Made by Mike_Zhang
感谢你的支持