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


简介

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

  1. 进行循环…

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

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/275556.html

(0)
上一篇 2022年7月20日
下一篇 2022年7月20日

相关推荐

发表回复

登录后才能评论