反向单链表 Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22605050/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Reverse Singly Linked List Java
提问by sammy333
Can someone tell me why my code dosent work? I want to reverse a single linked list in java: This is the method (that doesnt work correctly)
有人能告诉我为什么我的代码不起作用吗？我想在 java 中反转单个链表：这是方法（无法正常工作）
public void reverseList(){
Node before = null;
Node tmp = head;
Node next = tmp.next;
while(tmp != null){
if(next == null)
return;
tmp.next = before;
before = tmp;
tmp = next;
next = next.next;
}
}
And this is the Node class:
这是 Node 类：
public class Node{
public int data;
public Node next;
public Node(int data, Node next){
this.data = data;
this.next = next;
}
}
On input 4->3->2->1 I got output 4. I debugged it and it sets pointers correctly but still I dont get why it outputs only 4.
在输入 4->3->2->1 上，我得到了输出 4。我调试了它并且它正确设置了指针，但我仍然不明白为什么它只输出 4。
采纳答案by Joop Eggen
Node next = tmp.next;
while(tmp != null){
So what happens when tmp == null?
那么当 tmp == null 时会发生什么？
You almost got it, though.
不过，你几乎明白了。
Node before = null;
Node tmp = head;
while (tmp != null) {
Node next = tmp.next;
tmp.next = before;
before = tmp;
tmp = next;
}
head = before;
Or in nicer (?) naming:
或者更好的（？）命名：
Node reversedPart = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = reversedPart;
reversedPart = current;
current = next;
}
head = reversedPart;
ASCII art:
ASCII 艺术：
<__<__<__ __ : reversedPart : head
(__)__ __ __
head : current: > > >
回答by Shriram
Use this.
用这个。
if (current== null || current.next==null) return current;
Node nextItem = current.next;
current.next = null;
Node reverseRest = reverse(nextItem);
nextItem.next = current;
return reverseRest
回答by Pablo Francisco Pérez Hidalgo
I think your problem is that your initially last element nextattribute isn't being changed becuase of your condition
我认为你的问题是你最初的最后一个元素next属性没有因为你的条件而改变
if(next == null)
return;
Is at the beginning of your loop.
位于循环的开头。
I would move it right after tmp.next has been assigned:
我会在分配 tmp.next 后立即移动它：
while(tmp != null){
tmp.next = before;
if(next == null)
return;
before = tmp;
tmp = next;
next = next.next;
}
回答by Sean Paul
public void reverse() {
Node prev = null; Node current = head; Node next = current.next;
while(current.next != null) {
current.next = prev;
prev = current;
current = next;
next = current.next;
}
current.next = prev;
head = current;
}
回答by Ranjeet
public Node<E> reverseList(Node<E> node) {
if (node == null || node.next == null) {
return node;
}
Node<E> currentNode = node;
Node<E> previousNode = null;
Node<E> nextNode = null;
while (currentNode != null) {
nextNode = currentNode.next;
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
return previousNode;
}
回答by shailendra1118
I tried the below code and it works fine:
我尝试了下面的代码，它工作正常：
Node head = firstNode;
Node current = head;
while(current != null && current.next != null){
Node temp = current.next;
current.next = temp.next;
temp.next = head;
head = temp;
}
Basically one by one it sets the next pointer of one node to its next to next node, so from next onwards all nodes are attached at the back of the list.
基本上，它将一个节点的下一个指针设置为下一个节点的下一个节点，因此从下一个节点开始，所有节点都附加在列表的后面。
回答by prashant chaudhary
package com.three;
public class Link {
int a;
Link Next;
public Link(int i){
a=i;
}
}
public class LinkList {
Link First = null;
public void insertFirst(int a){
Link objLink = new Link(a);
objLink.Next=First;
First = objLink;
}
public void displayLink(){
Link current = First;
while(current!=null){
System.out.println(current.a);
current = current.Next;
}
}
public void ReverseLink(){
Link current = First;
Link Previous = null;
Link temp = null;
while(current!=null){
if(current==First)
temp = current.Next;
else
temp=current.Next;
if(temp==null){
First = current;
//return;
}
current.Next=Previous;
Previous=current;
//System.out.println(Previous);
current = temp;
}
}
public static void main(String args[]){
LinkList objLinkList = new LinkList();
objLinkList.insertFirst(1);
objLinkList.insertFirst(2);
objLinkList.insertFirst(3);
objLinkList.insertFirst(4);
objLinkList.insertFirst(5);
objLinkList.insertFirst(6);
objLinkList.insertFirst(7);
objLinkList.insertFirst(8);
objLinkList.displayLink();
System.out.println("-----------------------------");
objLinkList.ReverseLink();
objLinkList.displayLink();
}
}
回答by Sankalp
You can also try this
你也可以试试这个
LinkedListNode pointer = head;
LinkedListNode prev = null, curr = null;
/* Pointer variable loops through the LL */
while(pointer != null)
{
/* Proceed the pointer variable. Before that, store the current pointer. */
curr = pointer; //
pointer = pointer.next;
/* Reverse the link */
curr.next = prev;
/* Current becomes previous for the next iteration */
prev = curr;
}
System.out.println(prev.printForward());
回答by Oliver Hausler
If this isn't homework and you are doing this "manually" on purpose, then I would recommend using
如果这不是家庭作业并且您是故意“手动”执行此操作，那么我建议您使用
Collections.reverse(list);
Collections.reverse() returns void, and your list is reversed after the call.
Collections.reverse() 返回 void，并且您的列表在调用后反转。
回答by Jose Cifuentes
I know the recursive solution is not the optimal one, but just wanted to add one here:
我知道递归解决方案不是最佳解决方案，但只是想在这里添加一个：
public class LinkedListDemo {
static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return "" + val;
}
}
public static void main(String[] args) {
Node n = new Node(1, new Node(2, new Node(3, new Node(20, null))));
display(n);
n = reverse(n);
display(n);
}
static Node reverse(Node n) {
Node tail = n;
while (tail.next != null) {
tail = tail.next;
}
reverseHelper(n);
return (tail);
}
static Node reverseHelper(Node n) {
if (n.next != null) {
Node reverse = reverseHelper(n.next);
reverse.next = n;
n.next = null;
return (n);
}
return (n);
}
static void display(Node n) {
for (; n != null; n = n.next) {
System.out.println(n);
}
}
}
