单链表的反转,面试中的一个高频题目。当然也有很多变体,比如以k个结点为一组进行翻转链表的
需求
原链表中数据为:1->2->3->4
反转后链表中数据为:4->3->2->1
反转链表是有2种方法(递归法,遍历法)实现的
节点类设计
public class Node{ /**存储元素*/ public T item; /**记录下一个节点*/ public Node next; public Node(T t,Node next){ this.item = t; this.next = next; } }
递归反转其实就是从原链表的第一个存数据的结点开始,依次递归调用反转每一个结点, 直到把最后一个结点反转完毕,整个链表就反转完毕
public void reverse(){ //如果当前是空链表,不需要反转 if(this.n == 0){ return ; } reverse(head.next); } /**反转指定的结点curr,并把反转后的结点返回*/ public Node reverse(Node curr){ //已经到了最后一个元素 if(curr.next == null){ //反转后,头结点应该指向原链表中的最后一个元素 head.next = curr; return curr; } //递归的反转当前结点curr的下一个结点;返回值就是链表反转后,当前结点的上一个结点 Node pre = reverse(curr.next); //让返回的结点的下一个结点变为当前结点curr pre.next = curr; //把当前结点的下一个结点变为null curr.next = null; return curr; }
递归实质上就是系统帮你压栈的过程,系统在压栈的时候会保留现场
程序到达
Node pre= reverse(curr.next);
时进入递归假设此时递归到了3结点,此时curr=3结点,curr=3结点.next(实际上是4结点)
执行
Node pre= reverse(cur.next);
传入的curr.next是4结点,返回的curr是4结点接下来就是弹栈过程了
程序继续执行
pre.next = curr
就相当于4->3
curr.next = null
即把3结点指向4结点的指针断掉返回新链表的头结点curr
注意:当retuen后,系统会恢复2结点压栈时的现场,此时的curr=2结点;curr=2结点.next(3结点),再进行上述的操作
最后完成整个链表的翻转
遍历法就是在链表遍历的过程中将指针顺序置换
遍历过程
准备两个空结点 pre 用来保存先前结点、next 用来做临时变量
在头结点 node 遍历的时候此时为1结点
next = 1结点.next(2结点)
1结点.next=pre(null)
pre = 1结点
node = 2结点
进行下一次循环node=2结点
next = 2结点.next(3结点)
2结点.next=pre(1结点)=>即完成2->1
pre = 2结点
node = 3结点
进行循环...
public Node reverseList(Node node) { Node pre = null; Node next = null; while (node != null) { //永远指向当前节点cur的下一个节点 next = node.next; //反转的关键:当前的节点指向其前一个节点 node.next = pre; //更新pre和当前结点 pre = node; node = next; } //pre是反转之后的头节点 return pre; }