实现单向链表的反转

1.可以用临时变量前移方式逐步实现反转。

利用前中后三个临时变量，逐步前移并反转实现

public static <T> ListNode<T> reverseListTest1(ListNode<T> node){ ListNode<T> pre=null; ListNode<T> cur=node; ListNode<T> next=cur.next; while(next!=null){ pre=cur; cur=next; next=next.next; cur.next=pre; } node.next=null; return cur; } 2.可以利用递归的形式逐步逐步回调并反转

public static <T> ListNode<T> reverseListTest2(ListNode<T> node){ if (node.next!=null){ reverseListTest2(node.next).next=node; node.next=null; return node; } return node; }

说明：

1> 节点声明

class ListNode<T>{ T value; ListNode<T> next; public ListNode() { this(null); } public ListNode(T value) { this(value,null); } public ListNode(T value,ListNode<T> next) { this.value=value; this.next=next; } @Override public String toString() { return ""+value; } }

2>数据测试

public static void main(String[] args) { //创建单向链表，从0到10 ListNode<Integer> start=new ListNode<Integer>(10); ListNode<Integer> end=start; for (int i = 9; i >=0;--i) { ListNode<Integer> node=new ListNode<Integer>(i,start); start=node; } //反转单向链表，得到新根 ListNode<Integer> newRoot=reverseListTest1(start); while(newRoot!=null){ System.out.printf(newRoot+" "); newRoot=newRoot.next; } System.out.println(); //再次反转，反转前根为end，反转后根为start reverseListTest2(end); while(start!=null){ System.out.print(start+" "); start=start.next; } }

3>测试输出

10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10