Linked Lists Questions Part 1
152. (LC 21) Merge Two Sorted Lists
21. Merge Two Sorted Lists Easy
Keys (iterative approach)
-put the merged list into a new LL
-use tail = dummy (as iterator for the new list and making dummy point to the head of the new list)
-consider that l1, l2 can be of different len
### Solution 1
def mergeList(l1, l2):
dummy = ListNode()
tail = dummy #solution for making an empty node and making dummy.next point to newList head in one go
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next #we are given list HEADS, so we assign new head for l1
else:
tail.next = l2
l2 = l2.next
tail = tail.next #**
if l1: #if l1, l2 are of different sizes, stick the remainder of longer L to our new LL
tail.next = l1
if l2:
tail.next = l2
return dummy.next
### Solution 1-2 (Iterative)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
dummy = node = ListNode()
while list1 and list2:
if list1.val < list2.val:
node.next = list1
list1 = list1.next
else:
node.next = list2
list2 = list2.next
node = node.next
node.next = list1 or list2
return dummy.next
Iterative explained
dummy = node = ListNode()
Or
dummy = current_node
dummy = tail
Empty node for list start and current node that we will be moving.
return dummy.next
Because we are to return the head of the new merged list, if dummy.next is the head,
then dummy must be an empty node.
list1 = list1.next
Because initially we are given list1, list2 <<heads>>.
So list1 represents not the whole list, but list1’s head node.
So by list1=list1.next we set a different head for the list.
node.next = list1 or list2
Means the remaining of either list1 or list2.
I.e. for the situation when e.g.:
L1=1>2>3
L2=1>4>5>6>7
When we run out of nodes in L1, we just add the remainder of L2 to the answer List.
Python x = a or b
returns a if bool(a) evaluates True, else it evaluates b. Has the effect of returning the first item that evaluates True, or the last item (even if it evaluates to False).
Equivalent to: determination = arg_1 if arg_1 else arg_2 if arg_2 else ‘no arguments given!’
Solution 2 (Recursive)
# V1 [10]
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
lil.next = self.mergeTwoLists(lil.next, big)
return lil
# V2 [7]
class Solution:
def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
if list1 is None or list2 is None:
return list1 or list2
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
Iterative my versions:
### Iterative my V1 (LC accepted 92,71%)
def merge(l1, l2):
dummy = ListNode()
cur = dummy
while l1 or l2:
if not l1:
cur.next = l2
l2 = l2.next
elif not l2:
cur.next = l1
l1 = l1.next
elif l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next #<========*
return dummy.next
#*Remember that with e.g. cur.next=l2 we don’t yet move the node, just the pointer.
cur.next=l2
D—->L2
cur cur.next
cur=cur.next
D—->L2
cur
### My V2 iterative (LC accepted 75, 88)
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1 and not list2:
return None
if not list1:
return list2
if not list2:
return list1
dummy = ListNode()
l3 = ListNode()
dummy.next = l3
while list1 and list2:
if list1.val < list2.val:
l3.val = list1.val
list1 = list1.next
elif list2.val <= list1.val:
l3.val = list2.val
list2 = list2.next
if list1 and list2: #then making a new empty node
l3.next = ListNode()
l3 = l3.next
if list1 or list2:
l3.next = list1 if list1 else list2
return dummy.next
153. (LC 206) Reverse Linked List
LC 206. Reverse Linked List Easy
ITERATIVE
Keys:
-prev=None
Loop:
-use temp
-<point current to prev>
-shift prev/cur/temp
-return prev because that’s the new head (while current is pointing to None)
Solution [10]:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, curr = None, head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
The above is the iterative approach, T O(n) M O(1).
There is also recursive approach, but it is T O(n), M O(n).
RECURSIVE
### LC accepted 70, 60.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next) #1
head.next.next = head #2
head.next = None
return new_head #3
1->2->3->4
#1
Calling recursively on the sublist 2->3->4
# 1 -> 2->3->4
# h h.n
#2
After calling on the subproblem, what we are left to do is point 2 to 1, point 1 to None.
# 1 -> 2->3->4
# h h.n
# None <- 1 <- 2
2 = head.next
1 = head
To point 2 to 1: 2.next = 1, so head.next.next = head
#3
Because we need to return the head of the reversed LL.
We store the call to the function in a variable new_head, means it will store
the return value of the function when no subproblems left, when no head.next,
1>2>3>4, head=4, no head.next, so returns head, 4. And starts working on the call stack,
the actual reversing None<3<4, None<2<3<4, None<1<2<3<4.
154. (LC 92) Reverse Linked List II
Medium
Other names: Reverse sublist, reverse between
Hooks:
-left, right are integers, not nodes.
-So you reach the node at left with iteration.
-Don’t break the sublist from the main list. Keep the node before left pointing to
the node at left.
# Visualization
# 1 -> 2 -> 3 -> 4 -> 5
# L R
# prev<-|
# 1 -> 2 <- 3 <- 4 X 5
# |->prev
# 1 4 -> 3 -> 2 X 5
# |--------------^
# R L
# 1 -> 4 -> 3 -> 2 -> 5
After reversing the sublist between L-R:
(L->5) point the L node to the node immediately after R
(1->R) Node immediately before L point to R.
Solution [10]
# Python3
class Solution:
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
dummy = ListNode(0, head)
# 1) reach node at position "left"
leftPrev, cur = dummy, head
for i in range(left - 1):
leftPrev, cur = cur, cur.next
# Now cur="left", leftPrev="node before left"
# 2) reverse from left to right
prev = None
for i in range(right - left + 1):
tmpNext = cur.next
cur.next = prev
prev, cur = cur, tmpNext
# 3) Update pointers
leftPrev.next.next = cur # LP.next.next means pointing L.next to: cur which is node after "right"
leftPrev.next = prev # prev is "right"
return dummy.next
Explained
1) Reach node at L.
-dummy points to the head
-leftprev, with it we keep track of the node immediately before L
(after reaching L, we save it and not move it in the next step)
2) Reverse sublist L-R (iterating till R).
Just normal reverse.
temp = curr.next
curr.next = prev
prev = curr
curr = temp
3) Connect the reversed sublist L-R to the main list.
L->cur (point L to node after R, which is stored in cur)
leftPrev -> R (node before L point to R, R is stored in prev)
Connecting:
LeftPrev.next.next references the node at left because we didn’t disconnect the list.
Even after the reversal the node before left still points to the node at left.
# 1>2>3>4>5
# l r
# 1 4>3>2>
# |-----^
# And 4 still points to 5.
# 1 4>3>2>N 5
# |-------^
My rewrite
(mistakes: we don’t ever break any pointers of nodes, i.e. pointing them to None:
# beforeL.next = None <==Nope
# cur.next = None <==Nope
) (LC accepted)
# Python3
class Solution:
def reverseBetween(self, head: Optional[ListNode], L: int, R: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
beforeL = dummy
cur=head
for _ in range(L-1):
beforeL=cur
cur=cur.next
#reverse
prev=None
for _ in range(R-L+1):
tmp=cur.next
cur.next=prev
prev=cur
cur=tmp
beforeL.next.next=cur
beforeL.next=prev
return dummy.next
155. (LC 141) Linked List Cycle
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
Solution [10]:
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
My V (LC accepted 60, 90):
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = head.next
fast = head.next.next
while slow != fast:
if not fast or not fast.next:
break
slow = slow.next
fast = fast.next.next
return slow == fast
C++
// My V (LC accepted 40, 20)
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head || !head->next)
return false;
ListNode* slow = head->next;
ListNode* fast = head->next->next;
while(slow != fast){
if(!fast || !fast->next)
break;
slow = slow->next;
fast = fast->next->next;
}
return slow == fast;
}
};
Code for two methods: Hash and Floyd’s [14]
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node{
int data;
Node* next;
Node(int d=0): data(d), next(nullptr){} //constructor
};
//PRINT LL
void print_ll(Node* head){
Node *n = head; //dummy Node not to advance the head pointer
while(n){
cout << n->data << "->";
n = n->next;
}
cout << "NULL\n";
}
//HASH MAP
bool detect_loop_map(Node *head){
unordered_map<Node*, bool> visited;
Node *cur = head;
while(cur){
if(visited[cur])
return true;
visited[cur] = true;
cur = cur->next;
}
return false;
}
//FLOYD'S TWO POINTERS SLOW, FAST
bool detect_loop_floyd(Node *head){
Node * slow = head;
Node *fast = head;
while(slow && fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}
void create_loop(Node *head){
Node *cur = head;
while(cur->next){ //reach the last node
cur = cur->next;
}
cur->next = head->next; //point last node to the node after head
}
int main(){
//1->2->3->4->5->6->nullptr
Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6);
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = &n5;
n5.next = &n6;
Node *head = &n1;
//NO LOOP, check with 2 methods
bool hasloop = detect_loop_map(head);
cout << boolalpha << hasloop << endl; //false
hasloop = detect_loop_floyd(head);
cout << hasloop << endl; //false
//CREATE LOOP and check again with 2 methods
create_loop(head);
hasloop = detect_loop_map(head);
cout << hasloop << endl; //true
hasloop = detect_loop_floyd(head);
cout << hasloop << endl; //true
}
156. (LC 142) Linked List Cycle II
142. Linked List Cycle II Medium
Note on the task:
From the problem description you might think they want us to return the index of the node from which the cycle starts: Output: tail connects to node index 1. But from the code boilerplate we see that we are to return the node itself. +If no cycle, return None.
Solution 1 [2]
Keys:
-Is there a cycle
use S, F. Start both from head. While F.next and F.next.next loop till they meet.
-if S and F met, from that node:
2nd loop. Start S at head, F at where they met. Move each +1.
Where they meet again is the start of the cycle.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow is fast: # There is a cycle, so find cycle start
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next # both advance +1
return slow # where S and F meet
return None # no cycle
Solution 2
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
# If there is no cycle
if not fast or not fast.next:
return None
ans = head
while ans != slow:
ans = ans.next
slow = slow.next
return ans
Explained
-Find if it is a cycle (find node where fast and slow meet).
-separate block to return None if there is no cycle
-Finding cycle start. Set two pointers
1)where fast and slow met, e.g. take slow
2)set new pointer to the head of the entire list, e.g. ans
Move both slow and ans with the same speed. When they meet, that’s your starting
node of the cycle. (There is a “mathematical” reason why it is so.)
# a a1,s4
# s,f s1,f2 f1,s2 s3,f3
# 3-> 2 -> 0 -> -4
# ^--------------|
### My V (LC accepted 70, 60%)
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
slow, fast = head, head
while True:
try:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
except:
return None
ss1 = slow
ss2 = head
while ss1 != ss2:
ss1 = ss1.next
ss2 = ss2.next
return ss1
157. (LC 160) Intersection of Two Linked Lists
Easy
(Other names: Test for overlapping lists (lists are without cycle))
Notes on task interpretation [2]:
(Practical usage - reducing memory footprint.)
Intersection - node that is common to two lists.
Lists overlap if they have the same tail node.
(Also, once the lists converge at a node,they cannot diverge at a later node.)
O(m + n) time, space O(1)
Solution 1 [10]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(
self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
l1, l2 = headA, headB
while l1 != l2:
l1 = l1.next if l1 else headB #IMPORTANT if l1, not if l1.next
l2 = l2.next if l2 else headA
return l1
### My V (LC accepted 40,50%)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p1=headA
p2=headB
while p1 != p2:
if not p1: #when p1=None
p1 = headB #again, set p1 to headB, not p1.next
elif not p2:
p2 = headA
else:
p1=p1.next
p2=p2.next
return p1
Keys:
-two pointers
-increment +1
-achieving the len difference of lists:
switching to the head of the <opposite> list when pointer=None, i.e. reaches list end.
Why it does not make an infinite loop:
Because we allow pointers to slide off the respective list to None value before
pointing it to the head of the opposite list. Then at some point both l1, l2 will
be None, i.e. the same, even if lists don’t intersect.
We point l1, l2 to opposite heads just once.
After that, they are pointed to the same (their own) heads. If no intersection, they
will eventually run off the lists into None.
# _->_->
# _->_->_
# _->_->_->
# 1)We set p1, p2 to the heads of the respective nodes.
# p1_->_->
# _->_->_
# p2_->_->_->
# 2)Increment each +=1, until one p reaches the end of its respective end
# (p2 didn't yet reach the list end).
# _->_->
# _->p2_->p1_
# _->_->_->
# 3)Set that point to the head of the OPPOSITE list.
# _->_->
# _->_->p2_
# p1_->_->_->
# 4)When p2 reached the list end, set it to the head of the opposite list too.
# p2_->_->
# _->_->_
# _->p1_->_->
# 5)Loop goes on till node at p1 and p2 is the same
# _->_->
# p1,p2_->_->_
# _->_->_->
Alternative solution 1 (uses memory O(n)):
1)Hash set. Add nodes in L1 to a hash set.
2)Iterate L2 nodes. If node in hash, you have the intersect node.
Alternative solution 2
Similar, more verbose alternative to Solution 1 (the same efficiency and main logic as Solution 1).
1)Recognize that L1,L2 can have different lengths (as above, len 5, len 6).
2)Start p1 at the head of a shorter list. p2 at the head of the longer list.
3)Increment only p2 by the diff in len of the two lists.
4)Begin the main alg. Compare nodes at p1, p2. if not the same: +=1.
If the same, that’s your intersect node.
158. Intersection of Two Linked Lists - lists may have cycles
(Other names: Test for overlapping lists (lists may have cycles)) The same as the previous task. But this time one, both or non of the lists may have a cycle.
# A->B
# V
# C->D->E->F
# ^--------|
Both C and D are acceptable answers.
CASE ANALYSIS
=>Test each LL for cycles
(use 142. Linked List Cycle II, returns Node cycle start, or None if no cycle)
1)Neither list is cyclic ->
Then just use solution for ‘160 LC (157 My numbering). Intersection of Two Linked Lists (lists don’t have cycles)’
2)One is cyclic, the other is not. Then they cannot overlap. We are done.
3)Both are cyclic.
Subcases:
# 1/ cycles are disjoint. No overlap.
# 2/ Merge node is before the cycle start
# A->B
# V
# C->D->E->F
# ^--|
# 3/ Merge node is in the cycle
# A->B
# V
# C->D->E->F
# ^--------|
Solution 1
def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow is fast: # There is a cycle, so find cycle start
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next # both advance +1
return slow # where S and F meet
return None
def getIntersectionNode(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
l1, l2 = headA, headB
while l1 != l2:
l1 = l1.next if l1 else headB
l2 = l2.next if l2 else headA
return l1
def overlapping_lists(L1, L2):
# Find cycle starts if any
root1, root2 = detectCycle(L1), detectCycle(L2)
if not root1 and not root2: # Both L1, L2 no cycle
return getIntersectionNode(L1, L2) # Note, the func assumes they do overlap
elif (root1 and not root2) or (not root1 and root2): # Only 1 list has cycle, so no overlap
return None
# Both have cycles
# Test if they are not disjoint
# If overlap: Starting at the cycle start of L2, you should meet the cycle start of L1.
temp = root2
while True:
temp = temp.next
if temp is root1 or temp is root2:
break
if temp is not root1:
return None # Disjoint cycles
### One L has cycle
# Helper func. Distance from head to intersect node, i.e. unique stem_length
def distance(a, b):
dis = 0
while a is not b:
a = a.next
dis += 1
return dis
# Overlap before cycle start
stem1_length, stem2_length = distance(L1, root1), distance(L2, root2)
if stem1_length > stem2_length:
L2, L1 = L1, L2
root1, root2 = root2, root1
# List with longer unique stem, move it till both stems are the same dist from merge node **1
for _ in range(abs(stem1_length - stem2_length)):
L2 = L2.next
# Takes care of both: 1)when overlap is before cycle (overlap=L1==L2)
# 2)And the subcase when overlap is within the cycle (overlap=root1) **2
while L1 is not L2 and L1 is not root1 and L2 is not root2:
L1, L2 = L1.next, L2.next
return L1 if L1 is L2 else root1
#**1:
# L2
# (L1) A->B
# V
# (L2) L1 C->D->E->F (At E: root1, root2)
# ^--|
Pointers L2 at B and L1 at C are now the same distance from D (merge node). Now we just have to move them .next till L1=L2
#**2
Merge node is in the cycle.
A:root1, C:root2, if stem1_lenght > stem2_length, roots swap, making A:root2
# A->B
# V
# C->D->E->F
# ^--------|
Last comments [2]: If Ll == L2 before reaching root1, it means the overlap first occurs before the cycle starts; otherwise, the first overlapping node is not unique, we can return any node on the cycle.
159. (LC 143) Reorder List
143. Reorder List Medium
Quick notes:
-to find halves, iter1=head, iter2=head.next, while iter2 and iter2.next
-you are more likely to need
tmp = cur.next
than
tmp = cur
If you will be modifying cur later on.
### Solution 1 (My rewrite V1, LC accepted: Memory beats 94%, Time 40%)
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
""" Do not return anything, modify head in-place. """
slow=head
fast=head.next
#find 2 halves of the list
while fast and fast.next:
slow=slow.next
fast=fast.next.next
#reverse 2nd half
cur=slow.next # slow=B, slow.next=cur=C (start reversing at C)
slow.next=None # A>B C>D (breaking B>C link, B>None)
prev=None
while cur:
tmp=cur.next
cur.next=prev
prev=cur
cur=tmp
#merge half1 and half2 #1
cur1=head #head of half1
cur2=prev #head of half2
while cur2:
tmp1=cur1.next
tmp2=cur2.next
cur1.next=cur2
cur2.next=tmp1
cur1=tmp1
cur2=tmp2
# #1 Alternative merge
# iter1 = head
# iter2 = prev
# while iter2:
# nex = iter1.next
# iter1.next = iter2
# iter1 = iter2
# iter2 = nex
Explained
# Overview
Linked List
A>B>C>D
Where half would be.
A B | C D (For odd len list also: A B C | D E)
###1 Determine the half of the list. Use slow, fast pointers.
(Note, they begin at different positions.)
# A B C D
# S F
#
# A B C D
# S F
###2 We need to REVERSE THE 2ND HALF OF THE LIST.
The head of the 2nd list is at S.next
second = slow.next
The actual breaking of the original list consists in pointing the last node of the
first half to None. I.e. S.next=None
prev = slow.next = None
Recall how we reverse a LL (we use exactly the same code):
prev, curr = None, head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
###3 THE MERGE:
# After reversing the 2nd half we have:
# A>B C<D
# V V
# Memorize B, C
# A>B C<D
# V V
#
# Point head of L1 to head of L2.
# Point head of L2 to memorized L1.next.
# V---|
# A B C D
# |-----^
#
# Move heads of L1, L2 to memorized B, C.
# A>D>B C
# V V
# Merging in code
first, second = head, prev #prev is the last node in list (head of the 2nd half)
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
first, second = head, prev
Assign first and second to list heads.
first=A, second=D
while second:
Loop while 2nd list has no nodes.
tmp1, tmp2 = first.next, second.next
Put nodes after heads to temp vars.
tmp1=B, tmp2=C
first.next = second
second.next = tmp1
Point head of 1st list to head of 2nd list.
Point head of L2 to memorized L1.next.
first, second = tmp1, tmp2
Reassign heads of L1, L2.
Solution 1 formal
class Solution:
def reorderList(self, head: ListNode) -> None:
# find middle
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# reverse second half
second = slow.next #the starting point/node for the list 2nd half (where slow sopped + 1)
prev = slow.next = None #break list into 2 halves (pointing to None breaks the list)
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp
# merge two halves
first, second = head, prev #prev is the last node in list (head of the 2nd half)
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
160. (LC 237) Delete Node in a Linked List
237. Delete Node in a Linked List Medium
The input node is guaranteed not to be the tail node.
You are given the pointer to a node to delete.
-What’s the trouble?
Deleting a node usually requires modifying its predecessor’s next pointer and
the only way to get to the predecessor is to traverse the list from head,
which requires O(n) time.
-The trick.
Delete given node’s successor. Copy next node’s data into the current node. Delete next node.
This takes O(1).
class Solution:
def deleteNode(self, node_to_delete):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node_to_delete.val = node_to_delete.next.val
node_to_delete.next = node_to_delete.next.next
# OR
# def deleteNode(node):
# node.val = node.next.val
# node.next = node.next.next