Reversing single linked list in C#

Question

I am trying to reverse a linked list. This is the code I have come up with:

 public static void Reverse(ref Node root)
 {
      Node tmp = root;
      Node nroot = null;
      Node prev = null;

      while (tmp != null)
      {
          //Make a new node and copy tmp
          nroot = new Node();    
          nroot.data = tmp.data;

          nroot.next = prev;
          prev = nroot;   
          tmp = tmp.next;
       }
       root = nroot;            
  }

It is working well. Was wondering if it possible to avoid creating new node. Would like to have suggestions on this.

Why are you implementing a custom collection for this? Do none of the options available in the `System.Collections` namespace work for your requirements? — M.Babcock, Dec 31 '11 at 04:01

Eric Lippert · Answer 1 · 2011-12-31T05:07:28.853

60

That question gets asked a lot. When I was asked it in my interviews many years ago, I reasoned as follows: a singly-linked list is essentially a stack. Reversing a linked list is therefore a trivial operation on stacks:

newList = emptyList;
while(!oldList.IsEmpty())
    newList.Push(oldList.Pop());

Now all you have to do is implement IsEmpty and Push and Pop, which are one or two lines tops.

I wrote that out in about twenty seconds and the interviewer seemed somewhat perplexed at that point. I think he was expecting me to take about twenty minutes to do about twenty seconds work, which has always seemed odd to me.

edited Dec 31 '11 at 05:07

answered Dec 31 '11 at 04:54

Eric Lippert

647,829
179
1,238
2,067

+1 -- question: Wouldn't you also have to make sure `!=` is overloaded, so when `oldList` is empty, it registers as "equal to" `emptyList`? – Adam Rackis Dec 31 '11 at 05:05
@AdamRackis: Sure. Change it to `while(!oldList.IsEmpty())` if you prefer. This is pseudocode, not an actual implementation in any language. – Eric Lippert Dec 31 '11 at 05:06
Thanks @Eric - your pseudocode seems to be syntactically perfect C#, (which is hardly surprising) so I had to ask :) – Adam Rackis Dec 31 '11 at 05:08
8

@AdamRackis: It's also syntactically perfect JavaScript and C++ and probably a few other languages as well. :) – Eric Lippert Dec 31 '11 at 05:11
At first I thought this could be more memory intensive, but since you're destroying the old list at the same rate you're building up the new one, you just need to worry about how fast your push/pop operations on the stack are, but that's kind of a moot point, no? – Zach Folwick Feb 25 '15 at 06:21
1

@ZachFolwick: Performance considerations are of course important, but let's examine the supposition of the question; the supposition of the question is that maintaining a linked list -- a data structure with an overhead of one heap-allocated object for the node and one reference in the node *per collection item* -- is already a reasonable thing to do in the face of alternatives like arrays. In short, the supposition here is that memory is a cheap resource. So I don't mind burning a little if we have to. – Eric Lippert Feb 25 '15 at 16:22
I think there's an "in place" restriction that often gets placed on this kind of a question usually. – Vasily Sliounaiev Oct 11 '17 at 18:24
@VasilySliounaiev. You can implement push to store just the references to the original elements of the linked list. Then when popping, you update the "next" references. If you do it this way you are not creating a new copy, just reversing "in place" – Fracisco Ponce Gomez Mar 23 '18 at 00:00
The non-pseudocode version of this solution would be longer than any of the other solutions here. – Markus Oct 17 '18 at 20:01
3

@Markus: First, I doubt it. Some of these solutions are pretty long. Each stack operation is a couple lines. And for that utterly trivial cost, you get a stack ADT. **Reason about your code in terms of operations on abstract data types, not in terms of pointers and variables, and your code will become easier to understand**. An interviewer who is judging candidates on the basis of code golf is looking for the wrong signal. – Eric Lippert Oct 17 '18 at 20:18
3

@Markus: Here, let's fit it into a comment. We'll implement an immutable linked list first: `class Node { public T Head { get; private set; } public Node Tail { get; private set; } public static Node Empty = new Node(); private Node() {} public Node Push(T t) => new Node { Head = t, Tail = this } }` And now we implement a mutable `class List { private Node n = Node.Empty; public bool IsEmpty => n == Node.Empty; public void Push(T t) { n = n.Push(t); } public T Pop() { T h = n.Head; n = n.Tail; return h; }}` and we're done. – Eric Lippert Oct 17 '18 at 20:34
2

@Markus: Now we've got both mutable and immutable stacks. Each method is between one and three lines of code, and we can reason about the behaviour of the list in terms of the abstract operations, not in terms of how it is implemented with references and properties. That's not only far more fully featured than any of the other solutions posted here, it is also *shorter* than most of them, since apparently brevity is something you care about. – Eric Lippert Oct 17 '18 at 20:35
4

Now, of course in a proper implementation we would be good citizens and throw upon popping an empty stack, we would implement `IsEmpty` on the immutable stack, and lots of other features that would make this code longer. But making any code robust and fully featured makes it longer. My intention here is not to golf the shortest possible robust solution. It's to point out that when you move your coding up one semantic level, the code gets shorter and easier to understand *where it counts*. – Eric Lippert Oct 19 '18 at 22:27

score 55 · Accepted Answer · answered Dec 31 '11 at 04:07

55

Node p = root, n = null;
while (p != null) {
    Node tmp = p.next;
    p.next = n;
    n = p;
    p = tmp;
}
root = n;

answered Dec 31 '11 at 04:07

Sergey Kalinichenko

714,442
84
1,110
1,523

rasx · Answer 3 · 2014-08-29T15:20:09.967

9

Years ago I missed out on a hipster-L.A.-entertainment-company ASP.NET MVC developer position because I could not answer this question :( (It's a way to weed out non-computer-science majors.) So I am embarrassed to admit that it took me way too long to figure this out in LINQpad using the actual LinkedList<T>:

var linkedList = new LinkedList<int>(new[]{1,2,3,4,5,6,7,8,9,10});
linkedList.Dump("initial state");

var head = linkedList.First;
while (head.Next != null)
{
    var next = head.Next;
    linkedList.Remove(next);
    linkedList.AddFirst(next.Value);
}

linkedList.Dump("final state");

The read-only LinkedListNode<T>.Next property is what makes LinkedList<T> so important here. (Non-comp-sci people are encouraged to study the history of Data Structures---we are supposed to ask the question, Where does the linked list come from---why does it exist?)

edited Aug 29 '14 at 15:20

answered Aug 29 '14 at 15:03

rasx

5,288
2
45
60

2

Like you, I missed out an ASP.NET MVC developer position last week because of the same question about reversing a linked list :( – Andritchi Alexei Jan 27 '15 at 18:24
2

Good one! Although the reversing a linked list is a general problem, implementing it C# is a different and tricky compared to say C++ or Java because C#'s node does not allow setting next. So you have to get your head around setting next and think remove! – Higher-Kinded Type Sep 02 '16 at 07:28

score 6 · Answer 4 · answered Dec 31 '11 at 04:10

6

You don't need to make a copy. Some pseudo code:

prev = null;
current = head;
next = current->next;

(while next != null)
    current->next=prev
    prev=current
    current=next
    next=current->next

answered Dec 31 '11 at 04:10

ChrisWue

18,612
4
58
83

score 5 · Answer 5 · answered May 01 '19 at 20:40

This performed pretty well on Leetcode.

public ListNode ReverseList(ListNode head) {

        ListNode previous = null;
        ListNode current = head; 
        while(current != null) {
            ListNode nextTemp = current.next;
            current.next = previous;
            previous = current;
            current = nextTemp;
        }

        return previous;
    }

score 2 · Answer 6 · answered Dec 31 '11 at 04:04

Why not just have the head point at the tail, the tail point at the head, and go through the list reversing the direction in which prev points?

If you're not using a head and a tail, just go through the list reversing the prev relationships, and then make head point at the one that had a null prev when you got to it.

score 1 · Answer 7 · answered Mar 07 '13 at 07:56

1

public Node ReverseList(Node cur, Node prev)
    {
        if (cur == null) // if list is null
            return cur;

        Node n = cur.NextNode;
        cur.NextNode = prev;
        return (n == null) ? cur : ReverseList(n, cur);
    }

answered Mar 07 '13 at 07:56

Saboor Awan

1,567
4
24
37

1

cur seems to be the root - what is prev? – fubo Jun 08 '15 at 12:05

score 1 · Answer 8 · answered Mar 15 '15 at 01:54

Here a sample code to reverse a linked list.

using System;

class Program
{
    static void Main(string[] args)
    {
        LinkItem item = generateLinkList(5);
        printLinkList(item);
        Console.WriteLine("Reversing the list ...");
        LinkItem newItem = reverseLinkList(item);
        printLinkList(newItem);
        Console.ReadLine();
    }

    static public LinkItem generateLinkList(int total)
    {
        LinkItem item = new LinkItem();
        for (int number = total; number >=1; number--)
        {
            item = new LinkItem
            {
                name = string.Format("I am the link item number {0}.", number),
                next = (number == total) ? null : item
            };
        }
        return item;
    }

    static public void printLinkList(LinkItem item)
    {
        while (item != null)
        {
            Console.WriteLine(item.name);
            item = item.next;
        }
    }

    static public LinkItem reverseLinkList(LinkItem item)
    {
        LinkItem newItem = new LinkItem
        {
            name = item.name,
            next = null
        };

        while (item.next != null)
        {
            newItem = new LinkItem
            {
                name = item.next.name,
                next = newItem
            };

            item = item.next;
        }

        return newItem;
    }
}

class LinkItem
{
    public string name;
    public LinkItem next;
}

score 1 · Answer 9 · answered Jan 07 '17 at 14:15

linked list reversal recursive

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ReverseLinkedList
{
    class Program
    {
        static void Main(string[] args)
        {
            Node head = null;
            LinkedList.Append(ref head, 25);
            LinkedList.Append(ref head, 5);
            LinkedList.Append(ref head, 18);
            LinkedList.Append(ref head, 7);

            Console.WriteLine("Linked list:");
            LinkedList.Print(head);

            Console.WriteLine();
            Console.WriteLine("Reversed Linked list:");
            LinkedList.Reverse(ref head);
            LinkedList.Print(head);

            Console.WriteLine();
            Console.WriteLine("Reverse of Reversed Linked list:");
            LinkedList.ReverseUsingRecursion(head);
            head = LinkedList.newHead;
            LinkedList.PrintRecursive(head);
        }

        public static class LinkedList
        {
            public static void Append(ref Node head, int data)
            {
                if (head != null)
                {
                    Node current = head;
                    while (current.Next != null)
                    {
                        current = current.Next;
                    }

                    current.Next = new Node();
                    current.Next.Data = data;
                }
                else
                {
                    head = new Node();
                    head.Data = data;
                }
            }

            public static void Print(Node head)
            {
                if (head == null) return;
                Node current = head;
                do
                {
                    Console.Write("{0} ", current.Data);
                    current = current.Next;
                } while (current != null);
            }

            public static void PrintRecursive(Node head)
            {
                if (head == null)
                {
                    Console.WriteLine();
                    return;
                }
                Console.Write("{0} ", head.Data);
                PrintRecursive(head.Next);
            }

            public static void Reverse(ref Node head)
            {
                if (head == null) return;
                Node prev = null, current = head, next = null;
                while (current.Next != null)
                {
                    next = current.Next;
                    current.Next = prev;
                    prev = current;
                    current = next;
                }
                current.Next = prev;
                head = current;
            }

            public static Node newHead;

            public static void ReverseUsingRecursion(Node head)
            {
                if (head == null) return;
                if (head.Next == null)
                {
                    newHead = head;
                    return;
                }

                ReverseUsingRecursion(head.Next);
                head.Next.Next = head;
                head.Next = null;
            }
        }

        public class Node
        {
            public int Data = 0;
            public Node Next = null;
        }
    }
}

score 0 · Answer 10 · answered Jun 12 '16 at 01:45

Complexity O(n+m). Assuming head is the start node:

List<Node>Nodes = new List<Node>();
Node traverse= root;
while(traverse!=null)
{      
       Nodes.Add(traverse);
       traverse = traverse.Next;

}

int i = Nodes.Count - 1;     
root = Nodes[i];
for(; i>0; i--)
{
  Nodes[i].Next = Nodes[i-1];
}
Nodes[0].Next=null;

score 0 · Answer 11 · answered Nov 29 '18 at 09:36

0

In case you want a ready-made efficient implementation, I created an alternative to LinkedList that supports enumeration and reverse operations. https://github.com/NetFabric/NetFabric.DoubleLinkedList

answered Nov 29 '18 at 09:36

Antao Almada

445
5
12

score 0 · Answer 12 · answered Jan 16 '20 at 11:39

    public class Node<T>
    {
        public T Value { get; set; }
        public Node<T> Next { get; set; }
    } 

    public static Node<T> Reverse<T>(Node<T> head)
    {
        Node<T> tail = null;

        while(head!=null)
        {
            var node = new Node<T> { Value = head.Value, Next = tail };
            tail = node;
            head = head.Next;
        }

        return tail;
    }

score -3 · Answer 13 · edited Jan 15 '13 at 22:40

-3

The definition of ref is unnecessary because if you make the node as a reference type, it is OK to do:

public static void Reverse(Node root)

Also, the beauty of the interview question is less consumption of memory and in place reversal. Maybe a recursive way of doing it is also asked.

edited Jan 15 '13 at 22:40

KatieK

13,586
17
76
90

answered Jan 15 '13 at 22:21

bill

1

Reversing single linked list in C#

13 Answers13

linked list reversal recursive

Linked