Leetcode linked list problem collection (1)

  • 19.Remove Nth Node From End of List
  • 206.Reverse Linked List
  • 21.Merge Two Sorted Lists
  • 234.Palindrome Linked List
  • 141.Linked List Cycle
  • 203.Remove Linked List Elements
  • 83.Remove Duplicates from Sorted List
  • 2.Add Two Numbers
  • 876.Middle of the Linked List
  • 369.Plus One Linked List

19. Remove Nth Node From End of List

Two pointers solution: right pointer is n step behind left pointer. When right pointer reache the end of the linked list, left.next is the node that should be removed.
Hint: Dummy node usually very useful in linked list algorithms.

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    dummy = ListNode(next=head)       
    left = dummy
    right = left
    for _ in range(n):
        right = right.next
    
    while right.next:
        right = right.next
        left = left.next
    
    left.next = left.next.next
    return dummy.next

206. Reverse Linked List

Iterative

  • None -> 1 -> 2
  • None <- 1 2
  • None <- 1 <- 2

The key is use a pointer to track 2 while adjusting 1.next

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        
        while cur:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def reverseList(self, head: ListNode) -> ListNode:
    def reverse(pre: ListNode, cur:ListNode) -> ListNode:    
        if not cur:
            return
        nex = cur.next
        cur.next = pre
        reverse(cur, nex)  
        return cur
    
    if not head:
        return head
    tail = head
    while tail.next:
        tail = tail.next
    
    reverse(None, head)
    return tail

21. Merge Two Sorted Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    cur = ListNode()
    dummy = cur
    
    while l1 and l2:
        cur.next = ListNode()
        cur = cur.next
        if l1.val < l2.val:
            cur.val = l1.val
            l1 = l1.next
        else:
            cur.val = l2.val
            l2 = l2.next
    
    cur.next = l1 if l1 else l2
    return dummy.next

234. Palindrome Linked List

O(n) time

1
2
3
4
5
6
7
8
9
10
def isPalindrome(self, head: ListNode) -> bool:
    vals = []
    l = 0
    while head:
        l += 1
        vals.append(head.val)
        head = head.next
    a = vals[:l // 2]
    b = vals[l // 2 + l % 2:]
    return a == b[::-1]

141. Linked List Cycle

Technically is a hash table. tag visited.

1
2
3
4
5
6
7
8
9
10
def hasCycle(self, head: ListNode) -> bool:
    cur = ListNode(next=head)
    
    # set cur val to None if visited
    while cur.next:
        cur = cur.next
        if not cur.val:
            return True
        cur.val = None
    return False

Two pointers solution
This solution is more like an intelligence test. 🙃

1
2
3
4
5
6
7
8
9
10
11
12
13
def hasCycle(self, head: ListNode) -> bool:
    if not head:
        return False
    slow = head
    fast = head.next
    while (slow != fast):
        
        if not fast or not fast.next:
            # reach an end
            return False
        slow = slow.next
        fast = fast.next.next
    return True

203. Remove Linked List Elements

1
2
3
4
5
6
7
8
9
10
11
def removeElements(self, head: ListNode, val: int) -> ListNode:
    dummy = ListNode(next=head)
    pre = dummy
    cur = head
    while cur:
        if cur.val == val:
            pre.next = cur.next
        else:
            pre = pre.next
        cur = pre.next
    return dummy.next

83. Remove Duplicates from Sorted List

1
2
3
4
5
6
7
8
9
10
11
12
def deleteDuplicates(self, head: ListNode) -> ListNode:
    dummy = ListNode(next=head)
    pre, cur = dummy, head
    val = None
    while cur:
        if val == None or cur.val != val:
            val = cur.val
            pre = cur
        else:
            pre.next = cur.next
        cur = cur.next
    return dummy.next

2. Add Two Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    cur = dummy
    carry = 0
    while l1 or l2:
        if not l1:
            l1 = ListNode(0)
        if not l2:
            l2 = ListNode(0)
        val = l1.val + l2.val + carry
        carry = val // 10            
        cur.next = ListNode(val % 10)
        cur = cur.next
        l1 = l1.next
        l2 = l2.next
    if carry:
        cur.next = ListNode(carry)
    return dummy.next

876. Middle of the Linked List

O(n) time

1
2
3
4
5
6
7
8
9
10
def middleNode(self, head: ListNode) -> ListNode:
    l = 0
    mid = head
    cur = head
    while cur:
        l += 1
        cur = cur.next
        if not l % 2:
            mid = mid.next
    return mid

369. Plus One Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
def plusOne(self, head: ListNode) -> ListNode:
        
    def helper(node):
        if not node:
            return 0
        if not node.next:
            val = node.val + 1
        else:
            val = node.val + helper(node.next)
        node.val = val % 10
        return val // 10
    
    return ListNode(1, head) if helper(head) else head