Reverse Linked List

1. Problem Description

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

2. Approach

• Method 1: store nodes in a stack, then pop them to rebuild the list
• Method 2: three pointers

3. Implementation

3.1. Stack

• java

public class 反转链表
{
    public ListNode ReverseList(ListNode head)
    {
        // Check parameters
        if (head == null)
        {
            return null;
        }

        // Traverse the linked list and push nodes onto the stack
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode current = head;
        while (current != null)
        {
            stack.add(current);
            current = current.next;
        }

        // Keep popping nodes to rebuild the list
        ListNode newHead = stack.removeLast();
        ListNode now = newHead;
        while (!stack.isEmpty())
        {
            now.next = stack.removeLast();
            now = now.next;
        }
        now.next = null;

        return newHead;
    }
}

• go

// Store nodes in a stack first, then pop them and modify pointers
// Time: O(n)
// Space: O(n)
func ReverseList(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	nodes := make([]*ListNode, 0)
	n := pHead
	for n != nil {
		nodes = append(nodes, n)
		n = n.Next
	}

	newHead := nodes[len(nodes)-1]
	for i := len(nodes) - 1; i > 0; i-- {
		nodes[i].Next = nodes[i-1]
	}
	nodes[0].Next = nil

	return newHead
}

3.2. Three Pointers

• java

public class 反转链表2
{
    public ListNode ReverseList(ListNode head)
    {
        // Check parameters
        if (head == null)
        {
            return null;
        }

        // Three pointers point to the previous, current, and next nodes
        ListNode prev = null;
        ListNode current = head;
        ListNode next = current.next;
        //prev  current next
        //1   ->  2   ->  3   ->  4   ->  5   ->  6
        while (current != null)
        {
            current.next = prev;
            prev = current;
            current = next;
            if (current != null)
            {
                next = current.next;
            }
        }

        return prev;
    }
}

• go

// Three pointers
// Time: O(n)
// Space: O(1)
func ReverseList2(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}
	var pre *ListNode
	now := pHead
	next := pHead.Next

	for now != nil {
		now.Next = pre
		pre = now
		now = next
		if next != nil {
			next = next.Next
		}
	}

	return pre
}

4. References

• Reverse Linked List - NowCoder
• 206. Reverse Linked List - LeetCode