How to reverse a linked list

Given a linked list, return a reversed linked list

 

Example 1

Input:  1 -> 2 -> 3 -> null

Output: 3 -> 2 -> 1 -> null

Example 2

Input:  1 -> null

Output: 1 -> null

 

/* Definition for ListNode
public class ListNode
{
    public int Value;
    public ListNode Next;

    public ListNode(int x)
    {
        Value = x;
    }
}
*/
public class Solution
{
    public bool HasCycle(ListNode head)
    {
    }
}

Singly linked list is a sequence of data structures (nodes), which are connected together through links.

Head points to the first element of a linked list. After reversing the linked list, the head will point to the last node. (3)

Approach

The idea is to start from the tail equals null and add iteratively nodes one by one. for the 1 -> 2 -> 3 -> null linked list, the reversing process looks like this.

• null
• 1 -> null
• 2 -> 1 -> null
• 3 -> 2 -> 1 -> null

Code

    public ListNode Reverse(ListNode head)
    {
        if (head == null || head.Next == null)
        {
            return head;
        }

        ListNode tail = null;
        ListNode current = head;

        while (current != null)
        {
            ListNode next = current.Next;
            current.Next = tail;
            tail = current;
            current = next;
        }

        return tail;
    }

Time complexity: O(n).