迭代地反转单链表

必须是O（n）和就地（空间复杂度为1）。 下面的代码确实有效，但有更简单或更好的方法吗？

public void invert() { if (this.getHead() == null) return; if (this.getHead().getNext() == null) return; //this method should reverse the order of this linked list in O(n) time Node prevNode = this.getHead().getNext(); Node nextNode = this.getHead().getNext().getNext(); prevNode.setNext(this.getHead()); this.getHead().setNext(nextNode); nextNode = nextNode.getNext(); while (this.getHead().getNext() != null) { this.getHead().getNext().setNext(prevNode); prevNode = this.getHead().getNext(); this.getHead().setNext(nextNode); if (nextNode != null) nextNode = nextNode.getNext(); } this.head = prevNode; } 

Answer 1

编辑以删除每次迭代的额外比较：

  public void invert() { Node prev = null, next = null;; if (head == null) return; while (true) { next = head.getNext(); head.setNext(prev); prev = head; if (next == null) return; head = next; } } 

Answer 2

使用LinkedList的这个实现： https ： //stackoverflow.com/a/25311/234307

 public void reverse() { Link previous = first; Link currentLink = first.nextLink; first.nextLink = null; while(currentLink != null) { Link realNextLink = currentLink.nextLink; currentLink.nextLink = previous; previous = currentLink; first = currentLink; currentLink = realNextLink; } } 

Answer 3

这个怎么样：

 public void invert() { if (head != null) { for (Node tail = head.getNext(); tail != null; ) { Node nextTail = tail.getNext(); tail.setNext(head); head = tail; tail = nextTail; } } } 

Answer 4

使用自包含的实现，即List由头节点表示：

 public class Node { Node next; E value; public Node(E value, Node next) { this.value = value; this.next = next; } public Node reverse() { Node head = null; Node current = this; while (current != null) { Node save = current; current = current.next; save.next = head; head = save; } return head; } } 

Answer 5

 public void reverse(){ Node middle = head; Node last = head; Node first = null; while(last != null){ middle = last; last = last.next; middle.next = first; first = middle; } head = middle; } 

Answer 6

 public void invert() { if (first == null) return; Node prev = null; for ( Node next = first.next; next != null; next = first.next) { first.next = prev; prev = first; first = next; } first.next = prev; } 

Answer 7

修改节点类

你可以在Node类中覆盖toString方法来输入任何数据

public class Node { public Node node; private int data; Node(int data) { this.data = data; } @Override public String toString() { return this.data+""; }