当前位置:网站首页>Summary of common algorithms of linked list

Summary of common algorithms of linked list

2020-11-06 01:18:17 Clamhub's blog

1、 Sum two single linked lists

445. Addition of two numbers II
Better understanding of double stack method .

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
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Double stack method
LinkedList<ListNode> stack1 = new LinkedList<>();
LinkedList<ListNode> stack2 = new LinkedList<>();
ListNode res = null;
while (l1 != null) {
stack1.push(l1);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2);
l2 = l2.next;
}
// carry
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int sum = 0;
if (!stack1.isEmpty()) {
sum += stack1.pop().val;
}
if (!stack2.isEmpty()) {
sum += stack2.pop().val;
}
sum += carry;
// carry
carry = sum / 10;
// And modulus
ListNode node = new ListNode(sum % 10);
node.next = res;
res = node;
}
return res;
}

Construct two stacks from two linked lists , Use the first in, last out feature of the stack , Do two list flashbacks and do calculations , Pay attention to rounding .

2、 Single linked list non recursively flipped , Without the aid of other data structures

206. Reverse a linked list
The flip of single linked list is to flip the pointer of two adjacent nodes . Two extra pointers are needed to store the front and back nodes of the current node .

1
2
3
4
5
6
7
8
9
10
public static ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head!=null){
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}

3、 Palindrome list ( use O(n) Time complexity and O(1) Spatial complexity )

234. Palindrome list
Get the middle node position of the linked list through the fast and slow pointer , Reverse the second half of the list , After iteration, the linked list before and after , Whether the judgment value is the same .

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
public static boolean isPalindrome(ListNode head) {
// Boundary check , If the list is empty , Or just one node , Go straight back to true
if (head == null || head.next == null) {
return true;
}
// Use the fast and slow pointer to get the middle node position of the linked list
ListNode fast = head;
ListNode slow = head;
// When there are even nodes ,fast by null when , Reach the end point
// When you have an odd number of nodes ,fast.next by null, Reach the end point
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// At the end of the line , Odd number of nodes ,slow Right in the middle , Even number of nodes slow At the beginning of the second half .
//slow As the starting point of the first half of the linked list ,fast As the starting point of the second half of the linked list
fast = slow;
slow = head;
// reverse fast The second half of the list at the beginning
ListNode pre = null;
while (fast != null) {
ListNode temp = fast.next;
fast.next = pre;
pre = fast;
fast = temp;
}
// iteration slow And pre, Compare each value
while (slow != null && pre != null) {
if(slow.val!=pre.val){
return false;
}
slow = slow.next;
pre = pre.next;
}
return true;
}

4、 Circular list

141. Circular list
Check whether there are rings in the linked list , There are two ways : Use HashSet Or speed pointer .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean hasCycle(ListNode head) {
// Boundary check , If the linked list is empty or has only one node , Go straight back to false
if (head == null || head.next == null) {
return false;
}
// Use the speed pointer
ListNode fast = head.next;
ListNode slow = head;
// The fast and slow pointers don't coincide and they loop all the time
while (fast != slow) {
// As long as the fast pointer reaches the end of the list , Then there is no ring
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}

5、 Delete all the values in the linked list as val The node of

203. Remove linked list elements
A sentinel node is used to remove the linked list , Simplify the deletion of .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static ListNode removeElements(ListNode head, int val) {
// Use sentinel nodes
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode pre = sentinel;
while (head != null) {
// If the current node is the node to be deleted
if (head.val == val) {
// The previous node points directly to the next node
pre.next = head.next;
} else {
//pre Move backward
pre = head;
}
head = head.next;
}
return sentinel.next;
}

6、 Merge two ordered lists

21. Merge two ordered lists
Need to use sentinel node .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Defining sentinel nodes
ListNode head = new ListNode(0);
ListNode pre = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
if (l1 == null) {
pre.next = l2;
} else {
pre.next = l1;
}
return head.next;
}

summary

The commonly used algorithm of linked list often uses the fast and slow pointer and sentry node . Just use the sentinel node head There will be pre The nodes match .

tencent.jpg

版权声明
本文为[Clamhub's blog]所创,转载请带上原文链接,感谢

随机推荐