Ответ 1

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

Ответ 2

Этот вопрос задают много. Когда меня спросили об этом в моих интервью много лет назад, я рассуждал следующим образом: односвязный список по существу представляет собой стек. Таким образом, обращение к связанному списку является тривиальной операцией для стеков:

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

Теперь все, что вам нужно сделать, это реализовать IsEmpty и Push и Pop, которые являются одним или двумя строками.

Я написал это примерно через двадцать секунд, и интервьюер казался несколько озадаченным в тот момент. Я думаю, он ожидал, что я заберу около двадцати минут, чтобы сделать около двадцати секунд работы, что всегда казалось странным для меня.

Ответ 3

Несколько лет назад я упустил позицию разработчика ASP.NET MVC для хипстерской LA-индустрии развлечений, потому что не мог ответить на этот вопрос :( (Это способ отсеять не-компьютерные специальности). Поэтому мне стыдно признаться что мне потребовалось слишком много времени, чтобы понять это в 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> столь важным здесь. (Неопытным людям рекомендуется изучать историю структур данных - мы должны задать вопрос: откуда берется связанный список - почему он существует?)

Ответ 4

Вам не нужно делать копию. Некоторые псевдо-коды:

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

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

Ответ 5

Почему бы просто не иметь головную точку в хвосте, точку хвоста в голове и пройти через список, изменяющий направление, в котором находятся предыдущие точки?

Если вы не используете голову и хвост, просто перейдите в список, изменяющий предыдущие отношения, а затем сделайте головную точку той, у которой был нуль prev, когда вы добрались до нее.

Ответ 6

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

Ответ 7

Вот пример кода для обращения к связанному списку.

с помощью 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;
}

Ответ 8

реверсивный реверсивный список ссылок

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

Ответ 9

Это хорошо работает на 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;
    }     

Ответ 10

Сложность O (n + m). Предполагая, что голова - это начало 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;

Ответ 11

Если вам нужна готовая эффективная реализация, я создал альтернативу LinkedList, которая поддерживает перечисление и обратные операции. https://github.com/NetFabric/NetFabric.DoubleLinkedList

Ответ 12

Определение ref необязательно, потому что если вы создаете node как ссылочный тип, это нормально:

public static void Reverse(Node root)

Кроме того, красота вопроса интервью заключается в меньшем потреблении памяти и в обратном направлении. Возможно, рекурсивный способ сделать это также задан.