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