Linked List

Notes and typical questions for linked list related problems

Notes

• When deleting a node with a specific value

  • Consider adding a dummyHead to unify the deletion logic

  • Make sure every node is visited. When doing deletion, you may skip some nodes mistakenly

  • The return value should be a new head. Usually, the new head is gotten from a var that does not change instead of a var that keeps changing.

• When designing a linked list class with some actions,

  • Be careful about addAtTail implementation when size==0

  • Using a dummyHead can simplify most implementation

• Find mid node of a linked list

  • Without dummy head

      ListNode slow = head;
      ListNode fast = head;
  
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
      }
  
      // If the length of the list is even, slow points to 1st node of 2nd half of the list here
      // If the length of the list is odd, slow points to the exact mid node of the list here

  • With dummy head

     ListNode dummyHead = new ListNode(0);
     dummyHead.next = head;
     ListNode slow = dummyHead;
     ListNode fast = dummyHead;
  
     while (fast != null && fast.next != null) {
         slow = slow.next;
         fast = fast.next.next;
     }
  
     // If the length of the list is even, slow points to the last node of 1st half of the list here
     // If the length of the list is odd, slow points to the exact mid node of the list here

Typical Questions (18)

Other Linked List questions (4)

• LC 707. Design Linked List

  • Optimal Answer.

• LC 2130. Maximum Twin Sum of a Linked List

  • 🟠 Method 1: Mutate the original linked list.

    • Answer. TC: $O(n)$, SC: $O(1)$

  • Method 2: Not Mutate the original linked list.

    • Answer. TC: $O(n)$, SC: $O(n)$

• ⚪ LC 2. Add Two Numbers

  • Try not to do post-processing after while loop.

  • Optimal Answer. TC: $O(max(m,n))$, SC: $O(1)$ if not consider result space.

• ⚪ LC 138. Copy List with Random Pointer

  • Try to do it in 1 pass.

  • Answer. TC: $O(n)$, SC: $O(n)$

    • The optimal answer can only use constant space, but it will modify input data, and it will do it in multiple passes.

• ⚪ LC 160. Intersection of Two Linked Lists

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

Linked List Circle (2)

• LC 141. Linked List Cycle

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 142. Linked List Cycle II

  • 

  • Variables

    • x = length between start and entry point

    • y = length between circle entry and slow meet fast

    • z = length between slow meet fast and circle entry

    • t = time when slow node meet fast node

  • $2(x+y)=x+y+n(y+z) => x=(n-1)(y+z)+z$ 。

    • 由此推出x=z这个逻辑其实很绕。我换一个假设：$x-z=(n-1)(y+z)$。$t1$ 时刻慢指针再走 $z$ 步到达链入口。如果从入口点再走 $x-z$ 步依旧会在入口点（$x-z$ 是环长的整数倍数）。

    • 因此，$t$ 时刻，新node从start出发，slow node从“slow meet fast point”出发。等到slow到达circle entry时，新node距离circle entry还有 $x-z$ 步。由于 $x-z$ 是环长的整数倍数，当新node走到circle entry那一刻必定与slow node相遇。因此，由此可反推出新node与slow node相遇点一定为circle entry。

  • Optimal Answer. TC: $O(n)$, SC:

Linked List Manipulation (4)

• LC 24. Swap Nodes in Pairs

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 61. Rotate List

  • Try to only have 2 for/while loops.

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 86. Partition List

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🟠 LC 328. Odd Even Linked List

  • Its idea is tricky. Go through the linked list with lengths of 5 and 6 respectively to check the terminal condition of while loop.

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

Reverse Linked List (4)

• 🌟 LC 206. Reverse Linked List

  • Know both iterative and recursive solutions

  • Iterative Answer. TC: $O(n)$, SC: $O(1)$

  • Recursive Answer. TC: $O(n)$, SC: $O(n)$

• LC 92 Reverse Linked List II

  • Optimal Solution. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 25. Reverse Nodes in k-Group

  • I came up with approach 1 by myself!

  • Approach 1 with undo operation

    • Answer. TC: $O(n)$, SC: $O(1)$

  • 👍 Approach 2 without undo operation

    • Answer. TC: $O(n)$, SC: $O(1)$

• LC 234. Palindrome Linked List

  • Must modify the input linked list in place if we want to resolve it in SC $O(1)$

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

Remove List Node (4)

• LC 203. Remove Linked List Elements

  • Know both iterative and recursive solutions

• LC 19. Remove Nth Node From End of List

  • Use fast and slow pointers to reduce explored items !!!

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• LC 82. Remove Duplicates from Sorted List II

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• LC 2095. Delete the Middle Node of a Linked List

  • Dummy head node + 2 pointers. The solution is very clever by solving the question in 1 iteration

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$