Reverse Linked List

LeetCode

Commonly asked at:Amazon Meta Microsoft Apple

Reverse Linked List

Given the head of a singly linked list, reverse it and return the new head.

Example

Input: 1 2 3 4 5 Output: 5 4 3 2 1

Approach

Walk the list once, rewiring each node's next pointer to point backward to the previous node instead of forward. The classic trap: you must save a reference to the next node before overwriting current.next, or you lose the rest of the list permanently.

Walkthrough

python

1prev, curr = None, head
2while curr:
3    nxt = curr.next
4    curr.next = prev
5    prev = curr
6    curr = nxt
7return prev

Step 1 / 5

Save next=2, point 1.next backward to prev (None), then advance prev and curr.

Input format

Line 1: the list values, space-separated

Print the reversed list, space-separated.

Not solved yet

Ctrl+Enter

Editor

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    curr = head
    for v in values[1:]:
        curr.next = ListNode(v)
        curr = curr.next
    return head

values = list(map(int, input().split()))
head = build_list(values)
# TODO: iterative reversal — save next BEFORE overwriting current.next
prev, curr = None, head

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    curr = head
    for v in values[1:]:
        curr.next = ListNode(v)
        curr = curr.next
    return head

values = list(map(int, input().split()))
head = build_list(values)
# TODO: iterative reversal — save next BEFORE overwriting current.next
prev, curr = None, head

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    curr = head
    for v in values[1:]:
        curr.next = ListNode(v)
        curr = curr.next
    return head

values = list(map(int, input().split()))
head = build_list(values)
# TODO: iterative reversal — save next BEFORE overwriting current.next
prev, curr = None, head

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    curr = head
    for v in values[1:]:
        curr.next = ListNode(v)
        curr = curr.next
    return head

values = list(map(int, input().split()))
head = build_list(values)
# TODO: iterative reversal — save next BEFORE overwriting current.next
prev, curr = None, head

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.