Linked List
Today, let's talk about Linked List algorithms that are frequently used.
A Linked List is a data structure that stores data into a series of connected nodes, and thus it can be dynamically allocated. For each node, it contains 2 fields: the val that stores data, and the next that points to the next node.
In LeetCode, the Linked List is often defined below, using C++:
1struct ListNode {
2 int val;
3 ListNode *next;
4};
The content of this blog is shown below:
mindmap
root)Linked List(
A1(Node Removal)
A2(Inplace Reversal)
A3(Merge)
A4(Insertion Sort)
A5(Two Pointer)
Node Removal
LeetCode 203: Remove Linked List Elements
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.
1ListNode* removeElements(ListNode* head, int val){
2 ListNode newHead;
3 ListNode *pre = &newHead;
4 newHead.next = head;
5
6 while (pre->next != nullptr ) {
7 ListNode *cur = pre->next;
8 if (cur->val == val ) {
9 pre->next = cur->next;
10 delete cur;
11 }else
12 pre = pre->next;
13 }
14 return newHead.next;
15}
In-place Reversal
LeetCode 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
1ListNode* reverseList(ListNode* head) {
2 ListNode *pre = nullptr, *cur = head;
3 while (cur != nullptr ) {
4 ListNode *next = cur->next;
5 cur->next = pre;
6 pre = cur, cur = next;
7 }
8 return pre;
9}
Merge
LeetCode 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
1ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
2 ListNode head;
3 ListNode *pre = &head;
4
5 while (list1 != nullptr && list2 != nullptr ) {
6 if (list1->val < list2->val ) {
7 pre->next = list1;
8 list1 = list1->next;
9 } else {
10 pre->next = list2;
11 list2 = list2->next;
12 }
13 pre = pre->next;
14 }
15
16 while (list1 != nullptr ) {
17 pre->next = list1;
18 pre = pre->next;
19 list1 = list1->next;
20 }
21
22 while (list2 != nullptr ) {
23 pre->next = list2;
24 pre = pre->next;
25 list2 = list2->next;
26 }
27 pre->next = nullptr;
28 return head.next;
29}
Insertion Sort
LeetCode 147. Insertion Sort List
Given the head of a linked list, return the list after sorting it in ascending order.
Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.
The steps of the insertion sort algorithm:
- Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
- At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
- It repeats until no input elements remain.
1ListNode* insertionSortList(ListNode* head) {
2 if (head == nullptr) return head;
3 ListNode tmpHead;
4 ListNode *cur = head, *pre = &tmpHead;
5
6 while (cur != nullptr) {
7 while (pre->next != nullptr && pre->next->val < cur->val)
8 pre = pre->next;
9
10 ListNode* next = cur->next;
11 cur->next = pre->next;
12 pre->next = cur;
13 pre = &tmpHead;
14 cur = next;
15 }
16 return tmpHead.next;
17}
Two Pointer
We often use fast and slow to solve Linked List problems in $O(n)$-time complexity.
Middle Node
LeetCode 876. Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
1ListNode* middleNode(ListNode* head) {
2 ListNode *fast = head, *slow = head;
3 while (fast != nullptr && fast->next != nullptr) {
4 fast = fast->next->next;
5 slow = slow->next;
6 }
7 return slow;
8}
Cycle Detection
LeetCode 142. Linked List Cycle II
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
Do not modify the linked list.
1ListNode *detectCycle(ListNode *head) {
2 ListNode *fast = head, *slow = head;
3
4 // Judge if cycle exists
5 while ( true ) {
6 if (fast == nullptr || fast->next == nullptr )
7 return nullptr;
8 fast = fast->next->next;
9 slow = slow->next;
10 if (fast == slow) break; // Cycle detect
11 }
12
13 // yes there is a cycle, and find the entry of cycle
14 ListNode *ptr = head;
15 while (ptr != slow ) {
16 ptr = ptr->next;
17 slow = slow->next;
18 }
19 return ptr;
20}