Linked List Reverse

Table of Contents

• 206. Reverse Linked List (Easy)
• 92. Reverse Linked List II (Medium)
• 24. Swap Nodes in Pairs (Medium)
• 25. Reverse Nodes in k-Group (Hard)
• 2074. Reverse Nodes in Even Length Groups (Medium)

206. Reverse Linked List

• LeetCode | LeetCode CH (Easy)

• Tags: linked list, recursion

• Reverse a singly linked list.

graph LR
A((1)) --> B((2))
B --> C((3))
C --> D((4))
D --> E((5))

graph RL
E((5)) --> D((4))
D --> C((3))
C --> B((2))
B --> A((1))

206. Reverse Linked List - Python Solution

from typing import Optional

from template import ListNode


# Iterative
def reverseListIterative(head: Optional[ListNode]) -> Optional[ListNode]:
    cur = head
    prev = None

    while cur:
        temp = cur.next
        cur.next = prev

        prev = cur
        cur = temp

    return prev


# Recursive
def reverseListRecursive(head: Optional[ListNode]) -> Optional[ListNode]:
    def reverse(cur, prev):
        if not cur:
            return prev

        temp = cur.next
        cur.next = prev

        return reverse(temp, cur)

    return reverse(head, None)


nums = [1, 2, 3, 4, 5]
head1 = ListNode.create(nums)
print(head1)
# 1 -> 2 -> 3 -> 4 -> 5
print(reverseListIterative(head1))
# 5 -> 4 -> 3 -> 2 -> 1
head2 = ListNode.create(nums)
print(reverseListRecursive(head2))
# 5 -> 4 -> 3 -> 2 -> 1

92. Reverse Linked List II

• LeetCode | LeetCode CH (Medium)

• Tags: linked list

• Reverse a linked list from position left to position right. Return the linked list after reversing.

graph LR
A((1)) --> B((2))
B --> C((3))
C --> D((4))
D --> E((5))

graph LR
A((1)) --> B((4))
B --> C((3))
C --> D((2))
D --> E((5))

92. Reverse Linked List II - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def reverseBetween(
    head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    p0 = dummy
    for _ in range(left - 1):
        p0 = p0.next

    pre = None
    cur = p0.next
    for _ in range(right - left + 1):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt

    p0.next.next = cur
    p0.next = pre

    return dummy.next


head = ListNode().create([1, 2, 3, 4, 5])
left = 2
right = 4
print(reverseBetween(head, left, right))
# 1 -> 4 -> 3 -> 2 -> 5

24. Swap Nodes in Pairs

• LeetCode | LeetCode CH (Medium)

• Tags: linked list, recursion

• Given a linked list, swap every two adjacent nodes and return its head.

24. Swap Nodes in Pairs - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def swapPairs(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    n0 = dummy
    n1 = dummy.next

    while n1 and n1.next:
        n2 = n1.next
        n3 = n2.next

        n0.next = n2
        n2.next = n1
        n1.next = n3

        n0 = n1
        n1 = n3

    return dummy.next


nums = [1, 2, 3, 4, 5]
head = ListNode.create(nums)
print(head)
# 1 -> 2 -> 3 -> 4 -> 5
print(swapPairs(head))
# 2 -> 1 -> 4 -> 3 -> 5

25. Reverse Nodes in k-Group

• LeetCode | LeetCode CH (Hard)

• Tags: linked list, recursion

25. Reverse Nodes in k-Group - Python Solution

from typing import Optional

from template import ListNode


# Linked List
def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    n = 0
    cur = head
    while cur:
        n += 1
        cur = cur.next

    p0 = dummy = ListNode(next=head)
    pre = None
    cur = head

    while n >= k:
        n -= k
        for _ in range(k):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        nxt = p0.next
        nxt.next = cur
        p0.next = pre
        p0 = nxt

    return dummy.next


if __name__ == "__main__":
    head = [1, 2, 3, 4, 5]
    k = 2
    head = ListNode.create(head)
    print(head)  # 1 -> 2 -> 3 -> 4 -> 5
    print(reverseKGroup(head, k))  # 2 -> 1 -> 4 -> 3 -> 5

2074. Reverse Nodes in Even Length Groups

• LeetCode | LeetCode CH (Medium)

• Tags: linked list

Comments