java - 逆序链表

Question

我希望将按升序排列的链表倒置。我从最后一个节点开始，在最后一个节点(现在是头节点)之后插入第一个节点，但我不知道为什么它只是不打印任何东西，而是进入无限循环。我们只能使用单链表节点，不能使用迭代器。

public void reverse1() 
{
    if (head == null) 
    {
        return;
    }
    Node p = head;
    Node t= last;
    while(p != null && head!=last)
    {

         t.next = p;
         t=p;
         p = p.next;   
    }
   head = p;
   isAscending = false;
}

(我从插入方法获得的最后一个节点，只是将插入的最后一个节点设置为“最后一个”)

Answer 1

让我们分析一下你的逻辑

t=p; - 在此行之后 t 和 p 相等

p = p.next; - 自 t=p这一行相当于 p = t.next;

t.next = p; - 自 p = t.next;此行与 t.next = t.next; 相同

这行不通。试试这个吧

public void reverse1() {
  Node last = null;
  Node current = head;

  while(current != null) {
    Node next = current.next;
    current.next = last;
    last = current;
    current = next;
  }
}

编辑:

也许您应该使用递归解决方案。像这样:

public void reverse1() {
  if(isEmpty()) return;
  Node head = removeHead();
  reverse1();
  add(head);
}

这里我假设 removeHead() 返回头部并将其从列表中删除。 add() 将在末尾添加一个节点。