题 在C#中反转单个链表


我试图扭转一个链表。这是我提出的代码:

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

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


22
2017-12-31 03:57


起源


为什么要为此实现自定义集合?没有可用的选项 System.Collections 命名空间符合您的要求? - M.Babcock
我正在学习并准备面试。 - Nemo
Node在哪个命名空间? - Dave Lawrence


答案:


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

40
2017-12-31 04:07





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

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

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

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


47
2017-12-31 04:54



+1 - 问题:你不是也必须确定 != 超载,所以什么时候 oldList 是空的,它注册为“等于” emptyList? - Adam Rackis
@AdamRackis:好的。将其更改为 while(!oldList.IsEmpty()) 如果你更喜欢。这是伪代码,不是任何语言的实际实现。 - Eric Lippert
谢谢@Eric - 你的伪代码似乎在语法上完美C#,(这并不奇怪)所以我不得不问:) - Adam Rackis
@AdamRackis:它也是语法上完美的JavaScript和C ++,也可能是其他一些语言。 :) - Eric Lippert
这很有趣 - Nemo


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

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

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

6
2017-12-31 04:10





几年前,我错过了一个时髦的洛杉矶娱乐公司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人研究数据结构的历史 - 我们应该问这个问题, 链表 来自---它为什么存在?)


4
2017-08-29 15:03



和你一样,上周我错过了一个ASP.NET MVC开发者职位,因为有关逆转链表的问题:( - Andrițchi Alexei
好的!虽然反转链表是一个普遍的问题,但实现它C#与C ++或Java相比是不同的和棘手的,因为C#的节点不允许设置下一个。因此,您必须先了解下一步,并考虑删除! - Vivek Ragunathan


为什么不只是在尾部的头部点,头部的尾点,并通过列表反转prev点的方向?

如果你没有使用头部和尾部,只需通过反转prev关系的列表,然后在你到达时使用null上一个的头部。


2
2017-12-31 04:04



如何在O(N)中完成? - Nemo
那将是O(N)。 - Robert Allan Hennigan Leahy


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

1
2018-03-07 07:56



cur似乎是根源 - 什么是上一个? - fubo


这是一个反转链表的示例代码。

使用系统;

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

0
2018-03-15 01:54





复杂度O(n + m)。假设head是起始节点:

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;

0
2018-06-12 01:45





链表反转递归

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

0
2018-01-07 14:15