LC 19 & LC 24 & LC 203


Solution to LeetCode 19 Remove Nth Node From End of List, LeetCode 24 Swap Nodes in Pairs, and LeetCode 203 Remove Linked List Elements.

LeetCode 19

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

Double Pointers. 1) move the fast pointer n steps, 2) move the fast and slow pointer at the same time until the fast pointer’s next node is null, 3) remove the next node of the slow pointer, which is the nth node from the end

# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        slow, fast = dummy, dummy
        while n!=0:
            fast = fast.next
            n -= 1

        while fast.next != None:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

LeetCode 24

Swap Nodes in Pairs (Medium) [link]

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 swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        res = ListNode(next=head)
        pre = res
        while pre.next and pre.next.next:
            cur = pre.next
            post = pre.next.next

            cur.next = post.next
            post.next = cur
            pre.next = post

            pre = pre.next.next

        return res.next

LeetCode 203

Remove Linked List Elements (Easy) [link]

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 removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        cur = dummy_head

        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

  TOC