75 Leetcode Questions on Linked List
In this project, I will try to solve 75 Leetcode questions as listed in this link.
206. Reverse Linked List
DescriptionGiven the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return None
prev = None
curr = head
while curr is not None:
next = curr.next # save the next node
curr.next = prev # reverse the link
prev = curr # move backward one step
curr = next # move to the next node in the original list
return prev
141. Linked List Cycle
DescriptionGiven head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked-list.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# add a new attribute to the node when visited
while head is not None:
if hasattr(head, 'visited'):
return True
head.visited = True
head = head.next
return False
21. Merge Two Sorted Lists
DescriptionMerge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
Constraints:
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both l1 and l2 are sorted in non-decreasing order.
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
merged = ListNode()
head = merged
while list1 is not None and list2 is not None:
if list1.val < list2.val:
merged.next = list1
list1 = list1.next
else:
merged.next = list2
list2 = list2.next
merged = merged.next
if list1 is not None:
merged.next = list1
if list2 is not None:
merged.next = list2
return head.next
23. Merge k Sorted Lists
DescriptionYou are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length won’t exceed 10^4.
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
merged = ListNode()
head = merged
while list1 is not None and list2 is not None:
if list1.val < list2.val:
merged.next = list1
list1 = list1.next
else:
merged.next = list2
list2 = list2.next
merged = merged.next
if list1 is not None:
merged.next = list1
if list2 is not None:
merged.next = list2
return head.next
if len(lists) == 0:
return None
if len(lists) == 1:
return lists[0]
merged = lists[0]
for i in range(1, len(lists)):
merged = mergeTwoLists(merged, lists[i])
return merged
19. Remove Nth Node From End of List
DescriptionGiven the head of a linked list, remove the nth node from the end of the list and return its head.
Follow up: Could you do this in one pass?
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
Constraints:
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Using two-pointer method, with the distance between two-pointer is n.
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
output = head
second = head
for i in range(n):
second = second.next
if second is None:
return head.next
while second.next is not None:
head = head.next
second = second.next
head.next = head.next.next
return output
143. Reorder List
DescriptionYou are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 1000
Follow up: Can you solve the problem in O(1) extra space complexity and O(n) runtime complexity?
SolutionReverse the second half of the list, then merge two lists. Using two-pointer method to find the middle of the list.
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# find the middle of the list
slow = head # slow pointer
fast = head # fast pointer
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
# reverse the second half of the list
prev = None
while slow is not None:
next = slow.next # save the next node
slow.next = prev # reverse the link
prev = slow # move backward one step
slow = next # move to the next node in the original list
# merge two lists
# head is the first half of the list
# prev is the second half of the list
while prev.next is not None:
temp = head.next # save the next node in the first half
head.next = prev # link the first half to the second half
head = temp # move to the next node in the first half
temp = prev.next # save the next node in the second half
prev.next = head # link the second half to the first half
prev = temp # move to the next node in the second half
203. Remove Linked List Elements
DescriptionGiven 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.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
Constraints:
- The number of nodes in the list is in the range [0, 10^4].
- 1 <= Node.val <= 50
- 0 <= k <= 50
Iterative solution
There might be a case that:
-
[1, x, x, 2, 3, 4]: two or more consecutive nodes have to be removed. Therefore, we need two pointers,currto traverse the list, andprevto keep track of the previousvalidnode. Ifcurr == val, then we movecurrto the next node but keepprevunchanged. Ifcurr != val, then we linkprevtocurrand movecurrto the next node. -
[x, 1, 2, 3]: the first node has to be removed. To handle this case, we need to create a dummy node and link it to the head of the list.
So in total we need three pointers: dummy, prev and curr. We can use head as curr to save memory.
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
prev = dummy
while head is not None:
if head.val == val:
prev.next = head.next
else:
prev = head
head = head.next
return dummy.next
Recursive solution
Because we do the same task for head or head.next, we can use recursion to simplify the code.
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
def remove(head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
head.next = remove(head.next, val)
if head.val == val:
return head.next
else:
return head
remove(head, val)
# There is still a case when the first node has to be removed.
if head is not None and head.val == val:
return head.next
return head
or even simpler:
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
head.next = self.removeElements(head.next, val)
if head.val == val:
return head.next
else:
return head
But the recursive solution is slower and uses more memory than the iterative solution.
160. Intersection of Two Linked Lists
DescriptionGiven the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
It is guaranteed that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
- intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
- listA - The first linked list.
- listB - The second linked list.
- skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
- skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5].
There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references.
In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4].
There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4].
From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Constraints:
- The number of nodes of
listAis in them. - The number of nodes of
listBis in then. 1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA < m0 <= skipB < n-
intersectValis0iflistAandlistBdo not intersect. -
intersectVal == listA[skipA] == listB[skipB]iflistAandlistBintersect.
Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?
SolutionI gave up on this problem and found this beautiful solution here. The idea is to use two pointers, pA and pB, to traverse the two lists. When pA reaches the end of the list, we move it to the head of listB. Similarly, when pB reaches the end of the list, we move it to the head of listA. If there is an intersection, pA and pB will meet at the intersection. If there is no intersection, pA and pB will reach the end of the list at the same time.
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if headA is None or headB is None:
return None
pA = headA
pB = headB
while pA != pB:
pA = headB if pA is None else pA.next
pB = headA if pB is None else pB.next
return pA
2. Add Two Numbers
DescriptionYou are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
A simple solution is traverse the two lists and add the two numbers. The carry is passed to the next node.
def get_sum(a, b):
s = a + b
if s >= 10:
return s - 10, 1
else:
return s, 0
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
sum_head = ListNode()
curr = sum_head
carry = 0
while l1 is not None and l2 is not None:
val, carry = get_sum(l1.val + carry, l2.val)
curr.next = ListNode(val)
curr = curr.next
l1 = l1.next
l2 = l2.next
if l1 is not None:
while l1 is not None:
val, carry = get_sum(l1.val + carry, 0)
curr.next = ListNode(val)
curr = curr.next
l1 = l1.next
if l2 is not None:
while l2 is not None:
val, carry = get_sum(l2.val + carry, 0)
curr.next = ListNode(val)
curr = curr.next
l2 = l2.next
if carry == 1:
curr.next = ListNode(1)
return sum_head.next
Reflection: Linked List Problems
This is a placeholder for me to reflect what I have learned to solve the linked list problems. So far:
- Two-pointer method: using two-pointer to traverse the list, one pointer is faster than the other one. This method is used to find the middle of the list, or to find the nth node from the end of the list. This can also be used to find the intersection of two lists (see problem 160 above).
- Need to familiar with the basic operations of linked list: insert, delete, reverse, merge, etc.
Enjoy Reading This Article?
Here are some more articles you might like to read next: