JZ 24 | LC 206 & LC 19 & LC 876

Solution to JZ 24 (same as LeetCode 206 Reverse Linked List), LeetCode 19 Remove Nth Node From End of List, and LeetCode 876 Middle of the Linked List.

JZ 24 | LeetCode 206

Reverse the linked list (Easy). [NowCoder link] [LeetCode link]

1] Double pointer. Use double pointer pre and cur to reverse the linked list. nxt is needed to store cur.next, because after change the linker, the linked list is broken.

Time complexity O(n) due to iterating through the linked list, space complexity O(1) taken by pointers pre and cur.

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        if not head:
            return head
        cur = head
        pre = None
        while cur:
            nxt = cur.next # store the next value
            cur.next = pre # point cur.next to pre
            pre = cur # move pre to cur
            cur = nxt # move cur to cur.next
        return pre

2] Recursion also works but cannot pass because it takes space complexity of O(n) while the problem requires O(1).

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recursion(cur, pre):
            if not cur: 
                  return pre # terminate condition
            res = recursion(cur.next, cur) 
            cur.next = pre # change the linker 
            return res # return head
        return recur(head, None)

LeetCode 19

Remove Nth Node From End of List (Medium) [link]

Remove the length - n + 1 element from the linked list. Time complexity O(L). Space complexity O(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next # do not use head directly here
        
        dum = ListNode(0,head)
        cur = dum
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dum.next

Using double pointers, keep the distance of first and second to be n, so that when the first reaches the end, the second reach the number we want to remove. Time complexity O(L). Space complexity O(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second  = dummy

        for i in range(n):
            first = first.next
        
        while first:
            first = first.next
            second = second.next

        second.next = second.next.next
        return dummy.next

LeetCode 876

Middle of the Linked List (Easy) [link]

Iterate through the linked list, append element into a list. Time complexity O(n). Space complexity O(n).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]

Using double pointers. Time complexity O(n). Space complexity O(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        n, cur = 0, head
        while cur:
            n += 1
            cur = cur.next
        k, cur = 0, head
        while k < n // 2:
            k += 1
            cur = cur.next

        return cur