数据结构与算法–链表翻转

简介

单链表的反转，面试中的一个高频题目。当然也有很多变体，比如以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;
}

递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场

1. 程序到达Node pre= reverse(curr.next);时进入递归

2. 假设此时递归到了3结点，此时curr=3结点，curr=3结点.next(实际上是4结点)

3. 执行 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结点)，再进行上述的操作

最后完成整个链表的翻转

 方式二：循环遍历实现

 遍历法就是在链表遍历的过程中将指针顺序置换

遍历过程

1. 准备两个空结点 pre 用来保存先前结点、next 用来做临时变量

2. 在头结点 node 遍历的时候此时为1结点

   next = 1结点.next(2结点)

   1结点.next=pre(null)

   pre = 1结点

   node = 2结点

3. 进行下一次循环node=2结点

    next = 2结点.next(3结点)

    2结点.next=pre(1结点)=>即完成2->1

    pre = 2结点

    node = 3结点

4. 进行循环…

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;
}