Leetcode solution - linked list
- Leetcode solution - linked list
- 1. Find the intersection of two linked lists
- 2. Linked list inversion
- 3. Merge two ordered linked lists
- 4. Delete duplicate nodes from the ordered linked list
- 5. Delete the penultimate node of the linked list
- 6. Exchange adjacent nodes in the linked list
- 7. List summation
- 8. Palindrome linked list
- 9. Separate linked list
- 10. Linked list elements are clustered by parity
The linked list is an empty node, or has a value and a pointer to the next linked list, so many linked list problems can be handled by recursion.
1. Find the intersection of two linked lists
160. Intersection of Two Linked Lists (Easy)
For example, in the following example, A and B linked lists intersect at c1:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
However, the following intersection will not occur, because each node has only one next pointer, so there can only be one successor node. In the following example, node c has two successor nodes.
A: a1 → a2 d1 → d2
↘ ↗
c
↗ ↘
B: b1 → b2 → b3 e1 → e2
The time complexity is O(N) and the space complexity is O(1). null if no intersection exists.
Let the length of A be a + c and the length of B be b + c, where c is the length of the common part of the tail. It can be seen that a + c + b = b + c + a.
When the pointer accessing the list A accesses the tail of the list, make it access the list B from the head of the list B; Similarly, when the pointer accessing the B linked list accesses the tail of the linked list, make it access linked list A from the head of linked list A. In this way, you can control the pointer to access the two linked lists A and B, and access the intersection at the same time.
If there is no intersection, then a + b = b + a, l1 and l2 in the following implementation code will be null at the same time, so as to exit the loop.
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;
}
If you just judge whether there is an intersection, then there is another problem, that is Beauty of programming 3.6 Problems. There are two solutions:
- Connect the end of the first linked list to the beginning of the second linked list to see if there are rings in the second linked list;
- Or directly compare whether the last node of the two linked lists is the same.
2. Linked list inversion
206. Reverse Linked List (Easy)
recursion
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
ListNode newHead = reverseList(next);
next.next = head;
head.next = null;
return newHead;
}
Head insertion
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newHead.next;
newHead.next = head;
head = next;
}
return newHead.next;
}
3. Merge two ordered linked lists
21. Merge Two Sorted Lists (Easy)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
4. Delete duplicate nodes from the ordered linked list
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
5. Delete the penultimate node of the linked list
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) return head.next;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
6. Exchange adjacent nodes in the linked list
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
Topic requirements: the val value of the node cannot be modified, O(1) space complexity.
public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode pre = node;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next, l2 = pre.next.next;
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return node.next;
}
7. List summation
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
Title Requirements: the original linked list cannot be modified.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
ListNode head = new ListNode(-1);
int carry = 0;
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carry = sum / 10;
}
return head.next;
}
private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}
8. Palindrome linked list
234. Palindrome Linked List (Easy)
Subject requirements: solve with the spatial complexity of O(1).
Cut in half, reverse the second half, and then compare whether the two halves are equal.
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next; // Even nodes, let slow point to the next node
cut(head, slow); // Cut into two linked lists
return isEqual(head, reverse(slow));
}
private void cut(ListNode head, ListNode cutNode) {
while (head.next != cutNode) {
head = head.next;
}
head.next = null;
}
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
private boolean isEqual(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
9. Separate linked list
725. Split Linked List in Parts(Medium)
Input: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
Title Description: divide the linked list into k parts. The length of each part should be the same as possible. The length in the front should be greater than or equal to that in the back.
public ListNode[] splitListToParts(ListNode root, int k) {
int N = 0;
ListNode cur = root;
while (cur != null) {
N++;
cur = cur.next;
}
int mod = N % k;
int size = N / k;
ListNode[] ret = new ListNode[k];
cur = root;
for (int i = 0; cur != null && i < k; i++) {
ret[i] = cur;
int curSize = size + (mod-- > 0 ? 1 : 0);
for (int j = 0; j < curSize - 1; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return ret;
}
10. Linked list elements are clustered by parity
328. Odd Even Linked List (Medium)
Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}