在C#中反转单个链表

Question

我试图扭转链表.这是我提出的代码:

 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;            
  }

它运作良好.想知道是否有可能避免创建新节点.想对此有所建议.

Answer 1

这个问题被问了很多.当我多年前在我的采访中被问到这个问题时,我的理由如下:单链表基本上是一个堆栈.因此,反转链表是堆栈上的一个简单操作:

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

现在你所要做的就是实现IsEmpty和Push and Pop,它们是一行或两行的顶部.

我在大约二十秒内把它写出来,面试官在那一点似乎有些困惑.我想他希望我花大约20分钟做大约20秒的工作,这对我来说一直都很奇怪.

Answer 2

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

Answer 3

几年前，我错过了一个时髦的LA-娱乐公司ASP.NET MVC开发人员的职位，因为我无法回答这个问题：（（这是一种淘汰非计算机科学专业的方法。）所以我很尴尬地承认我花了很长时间才在LINQpad中使用实际的方法解决这个问题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");

只读LinkedListNode<T>.Next属性LinkedList<T>在这里非常重要。（鼓励非comp-sci人研究数据结构的历史-我们应该问一个问题，链表从何而来-为什么会存在？）

Answer 4

您无需复制.一些伪代码:

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

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

Answer 5

这在 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;
    }