反向单链表Java
有人能告诉我为什么我的代码有效吗？ 我想在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; } } 这是Node类：
public class Node{ public int data; public Node next; public Node(int data, Node next){ this.data = data; this.next = next; } }
在输入4-> 3-> 2-> 1我得到输出4.我调试它并正确设置指针，但我仍然不明白为什么它只输出4。
Node next = tmp.next; while(tmp != null){
那么当tmp == null时会发生什么？
但你几乎得到了它。
Node before = null; Node tmp = head; while (tmp != null) { Node next = tmp.next; tmp.next = before; before = tmp; tmp = next; } head = before;
或者更好（？）命名：
Node reversedPart = null; Node current = head; while (current != null) { Node next = current.next; current.next = reversedPart; reversedPart = current; current = next; } head = reversedPart;
ASCII艺术：
<__<__<__ __ : reversedPart : head (__)__ __ __ head : current:> > >
public Node reverseList(Node node) { if (node == null || node.next == null) { return node; } Node currentNode = node; Node previousNode = null; Node nextNode = null; while (currentNode != null) { nextNode = currentNode.next; currentNode.next = previousNode; previousNode = currentNode; currentNode = nextNode; } return previousNode; }
反转链表的方法如下：
反向方法
public void reverseList() { Node curr = head; Node pre = null; Node incoming = null; while(curr != null) { incoming = curr.next; // store incoming item curr.next = pre; // swap nodes pre = curr; // increment also pre curr = incoming; // increment current } head = pre; // pre is the latest item where // curr is null }
反转列表需要三个引用： pre ， curr ， incoming
... pre curr incoming ... --> (n-1) --> (n) --> (n+1) --> ...
要反转一个节点，你必须存储前一个元素，这样你就可以使用简单的东西;
curr.next = pre;
扭转当前元素的方向。 但是，要迭代列表，您必须在执行上述语句之前存储传入元素，因为当反转当前元素的下一个引用时，您不再知道传入元素，这就是需要第三个引用的原因。
演示代码如下;
LinkedList样本类
public class LinkedList { protected Node head; public LinkedList() { head = null; } public LinkedList(E[] list) { this(); addAll(list); } public void addAll(E[] list) { for(int i = 0; i < list.length; i++) add(list[i]); } public void add(E e) { if(head == null) head = new Node (e); else { Node temp = head; while(temp.next != null) temp = temp.next; temp.next = new Node (e); } } public void reverseList() { Node curr = head; Node pre = null; Node incoming = null; while(curr != null) { incoming = curr.next; // store incoming item curr.next = pre; // swap nodes pre = curr; // increment also pre curr = incoming; // increment current } head = pre; // pre is the latest item where // curr is null } public void printList() { Node temp = head; System.out.print("List: "); while(temp != null) { System.out.print(temp + " "); temp = temp.next; } System.out.println(); } public static class Node { protected E e; protected Node next; public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } } }
测试代码
public class ReverseLinkedList { public static void main(String[] args) { Integer[] list = { 4, 3, 2, 1 }; LinkedList linkedList = new LinkedList (list); linkedList.printList(); linkedList.reverseList(); linkedList.printList(); } }
产量
List: 4 3 2 1 List: 1 2 3 4
如果这不是作业，而你是故意“手动”这样做，那么我建议使用
Collections.reverse(list);
Collections.reverse（）返回void，调用后您的列表会反转。
我们可以有三个节点，包括current，current和next。
public void reverseLinkedlist() { /* * Have three nodes ie previousNode,currentNode and nextNode When currentNode is starting node, then previousNode will be null Assign currentNode.next to previousNode to reverse the link. In each iteration move currentNode and previousNode by 1 node. */ Node previousNode = null; Node currentNode = head; while (currentNode != null) { Node nextNode = currentNode.next; currentNode.next = previousNode; previousNode = currentNode; currentNode = nextNode; } head = previousNode; }
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; }
我知道递归解决方案不是最优解决方案，但只是想在这里添加一个：
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); } } }
我不明白……为什么不这样做：
private LinkedList reverseLinkedList(LinkedList originalList){ LinkedList reversedList = new LinkedList<>(); for(int i=0 ; i
我发现这更容易。
更优雅的解决方案是使用递归
void ReverseList(ListNode current, ListNode previous) { if(current.Next != null) { ReverseList(current.Next, current); ListNode temp = current.Next; temp.Next = current; current.Next = previous; } }
我尝试了以下代码，它工作正常：
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; }
基本上它一个接一个地将一个节点的下一个指针设置到下一个节点的下一个节点，因此从下一个开始，所有节点都附加在列表的后面。
Node reverse_rec(Node start) { if (start == null || start -> next == null) { return start; } Node new_start = reverse(start->next); start->next->next = start; start->next = null; return new_start; } Node reverse(Node start) { Node cur = start; Node bef = null; while (cur != null) { Node nex = cur.next; cur.next = bef; bef = cur; cur = nex; } return bef; }
我认为你的问题是你最初的最后一个元素下一个属性没有被改变，因为你的情况
if(next == null) return;
在你的循环开始。
我会在分配tmp.next后立即移动它：
while(tmp != null){ tmp.next = before; if(next == null) return; before = tmp; tmp = next; next = next.next; }
用这个。
if (current== null || current.next==null) return current; Node nextItem = current.next; current.next = null; Node reverseRest = reverse(nextItem); nextItem.next = current; return reverseRest
或Java程序来反转单链接列表
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(); } }
你也可以试试这个
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());
package LinkedList; import java.util.LinkedList; public class LinkedListNode { private int value; private LinkedListNode next = null; public LinkedListNode(int i) { this.value = i; } public LinkedListNode addNode(int i) { this.next = new LinkedListNode(i); return next; } public LinkedListNode getNext() { return next; } @Override public String toString() { String restElement = value+"->"; LinkedListNode newNext = getNext(); while(newNext != null) {restElement = restElement + newNext.value + "->"; newNext = newNext.getNext();} restElement = restElement +newNext; return restElement; } public static void main(String[] args) { LinkedListNode headnode = new LinkedListNode(1); headnode.addNode(2).addNode(3).addNode(4).addNode(5).addNode(6); System.out.println(headnode); headnode = reverse(null,headnode,headnode.getNext()); System.out.println(headnode); } private static LinkedListNode reverse(LinkedListNode prev, LinkedListNode current, LinkedListNode next) { current.setNext(prev); if(next == null) return current; return reverse(current,next,next.getNext()); } private void setNext(LinkedListNode prev) { this.next = prev; } }
public class ReverseLinkedList { public static void main(String args[]){ LinkedList linkedList = new LinkedList (); linkedList.add("a"); linkedList.add("b"); linkedList.add("c"); linkedList.add("d"); linkedList.add("e"); linkedList.add("f"); System.out.println("Original linkedList:"); for(int i = 0; i <=linkedList.size()-1; i++){ System.out.println(" - "+ linkedList.get(i)); } LinkedList reversedlinkedList = reverse(linkedList); System.out.println("Reversed linkedList:"); for(int i = 0; i <=reversedlinkedList.size()-1; i++){ System.out.println(" - "+ reversedlinkedList.get(i)); } } public static LinkedList reverse(LinkedList linkedList){ for(int i = 0; i < linkedList.size()/2; i++){ String temp = linkedList.get(i); linkedList.set(i, linkedList.get(linkedList.size()-1-i)); linkedList.set((linkedList.size()-1-i), temp); } return linkedList; } }
要反转单链表，您应该有三个节点， top ， beforeTop和AfterTop 。 Top是单链表的标题，因此beforeTop将为null， afterTop将成为top的下一个元素，并且每次迭代前移topTop分配top和top分配afterTop （即top.next ）。
private static Node inverse(Node top) { Node beforeTop=null, afterTop; while(top!=null){ afterTop=top.next; top.next=beforeTop; beforeTop=top; top=afterTop; } return beforeTop; }
使用递归这太容易了：
package com.config; import java.util.Scanner; public class Help { public static void main(String args[]){ Scanner sc = new Scanner(System.in); Node head = null; Node temp = null; int choice = 0; boolean flage = true; do{ Node node = new Node(); System.out.println("Enter Node"); node.data = sc.nextInt(); if(flage){ head = node; flage = false; } if(temp!=null) temp.next = node; temp = node; System.out.println("Enter 0 to exit."); choice = sc.nextInt(); }while(choice!=0); Help.getAll(head); Node reverse = Help.reverse(head,null); //reverse = Help.reverse(head, null); Help.getAll(reverse); } public static void getAll(Node head){ if(head==null) return ; System.out.println(head.data+"Memory Add "+head.hashCode()); getAll(head.next); } public static Node reverse(Node head,Node tail){ Node next = head.next; head.next = tail; return (next!=null? reverse(next,head) : head); } } class Node{ int data = 0; Node next = null; }
// Java program for reversing the linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to reverse the linked list Node reverse(Node node) { Node prev = null; Node current = node; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } node = prev; return node; } // prints content of double linked list void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(85); list.head.next = new Node(15); list.head.next.next = new Node(4); list.head.next.next.next = new Node(20); System.out.println("Given Linked list"); list.printList(head); head = list.reverse(head); System.out.println(""); System.out.println("Reversed linked list "); list.printList(head); } } OUTPUT: - Given Linked list 85 15 4 20 Reversed linked list 20 4 15 85
Node Reverse(Node head) { Node n,rev; rev = new Node(); rev.data = head.data; rev.next = null; while(head.next != null){ n = new Node(); head = head.next; n.data = head.data; n.next = rev; rev = n; n=null; } return rev; }
使用上述function可以反转单个链表。
public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; }
查看有关复杂性分析的更多详细信息http://javamicro.com/ref-card/DS-Algo/How-to-Reverse-Singly-Linked-List ？
public static LinkedList reverseLinkedList(LinkedList node) { if (node == null || node.getNext() == null) { return node; } LinkedList remaining = reverseLinkedList(node.getNext()); node.getNext().setNext(node); node.setNext(null); return remaining; }
/** * Reverse LinkedList * @author asharda * */ class Node { int data; Node next; Node(int data) { this.data=data; } } public class ReverseLinkedList { static Node root; Node temp=null; public void insert(int data) { if(root==null) { root=new Node(data); } else { temp=root; while(temp.next!=null) { temp=temp.next; } Node newNode=new Node(data); temp.next=newNode; } }//end of insert public void display(Node head) { while(head!=null) { System.out.println(head.data); head=head.next; } } public Node reverseLinkedList(Node head) { Node newNode; Node tempr=null; while(head!=null) { newNode=new Node(head.data); newNode.next=tempr; tempr=newNode; head=head.next; } return tempr; } public static void main(String[] args) { ReverseLinkedList r=new ReverseLinkedList(); r.insert(10); r.insert(20); r.insert(30); r.display(root); Node t=r.reverseLinkedList(root); r.display(t); } }
public class SinglyLinkedListImpl { private Node head; public void add(T element) { Node item = new Node (element); if (head == null) { head = item; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = item; } } private void reverse() { Node temp = null; Node next = null; while (head != null) { next = head.next; head.next = temp; temp = head; head = next; } head = temp; } void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } public static void main(String a[]) { SinglyLinkedListImpl sl = new SinglyLinkedListImpl (); sl.add(1); sl.add(2); sl.add(3); sl.add(4); sl.printList(sl.head); sl.reverse(); sl.printList(sl.head); } static class Node { private T data; private Node next; public Node(T data) { super(); this.data = data; } } }
public class Linkedtest { public static void reverse(List
这对任何类型的集合Object都很有用。