讨论/《初级算法》 - 反转链表/
《初级算法》 - 反转链表
共 47 个回复

1,使用栈解决

链表的反转是老生常谈的一个问题了,同时也是面试中常考的一道题。最简单的一种方式就是使用,因为栈是先进后出的。实现原理就是把链表节点一个个入栈,当全部入栈完之后再一个个出栈,出栈的时候在把出栈的结点串成一个新的链表。原理如下
image.png
代码比较简单,来看下

public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈,然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点,一定要让他的next
    //等于空,否则会构成环
    node.next = null;
    return dummy;
}

看一下运行结果
image.png


2,双链表求解

双链表求解是把原链表的结点一个个摘掉,每次摘掉的链表都让他成为新的链表的头结点,然后更新新链表。下面以链表1→2→3→4为例画个图来看下。
image.png
image.png
他每次访问的原链表节点都会成为新链表的头结点,最后再来看下代码

public ListNode reverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点,保存起来
        //留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点,
        //其实就是把新链表挂到访问的原链表节点的
        //后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值,继续访问
        head = temp;
    }
    //返回新链表
    return newHead;
}

看下运行结果
image.png


3,递归解决

之前我写过一篇文章什么是递归,通过这篇文章,让你彻底搞懂递归,里面讲了递归的模板,终止条件,递归调用,逻辑处理。

public ListNode reverseList(参数0) {
    if (终止条件)
        return;

    逻辑处理(可能有,也可能没有,具体问题具体分析)

    //递归调用
    ListNode reverse = reverseList(参数1);

    逻辑处理(可能有,也可能没有,具体问题具体分析)
}

终止条件就是链表为空,或者是链表没有尾结点的时候,直接返回

if (head == null || head.next == null)
    return head;

递归调用是要从当前节点的下一个结点开始递归。逻辑处理这块是要把当前节点挂到递归之后的链表的末尾,看下代码

public ListNode reverseList(ListNode head) {
    //终止条件
    if (head == null || head.next == null)
        return head;
    //保存当前节点的下一个结点
    ListNode next = head.next;
    //从当前节点的下一个结点开始递归调用
    ListNode reverse = reverseList(next);
    //reverse是反转之后的链表,因为函数reverseList
    // 表示的是对链表的反转,所以反转完之后next肯定
    // 是链表reverse的尾结点,然后我们再把当前节点
    //head挂到next节点的后面就完成了链表的反转。
    next.next = head;
    //这里head相当于变成了尾结点,尾结点都是为空的,
    //否则会构成环
    head.next = null;
    return reverse;
}

因为递归调用之后head.next节点就会成为reverse节点的尾结点,我们可以直接让head.next.next = head;,这样代码会更简洁一些,看下代码

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode reverse = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reverse;
}

看下运行结果
image.png


这种递归往下传递的时候基本上没有逻辑处理,当往回反弹的时候才开始处理,也就是从链表的尾端往前开始处理的。我们还可以再来改一下,在链表递归的时候从前往后处理,处理完之后直接返回递归的结果,这就是所谓的尾递归,这种运行效率要比上一种好很多

public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

再来看一下运行结果
image.png

尾递归虽然也会不停的压栈,但由于最后返回的是递归函数的值,所以在返回的时候都会一次性出栈,不会一个个出栈这么慢。但如果我们再来改一下,像下面代码这样又会一个个出栈了

public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    ListNode node = reverseListInt(next, head);
    return node;
}


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

29
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* p = head;
    struct ListNode* q = NULL;
    struct ListNode* t = NULL;
    while(p){ 
        t = p;
        p = p -> next;
        t -> next = q;
        q = t;
    }
    return q;
}
10
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 基本思路是:两个指针,将后面的指针cur指向前一个指针pre实现节点反转
        // 前一个指针pre 
        ListNode pre = null;
        // 后一个指针cur
        ListNode cur = head;
        // 临时指针 temp 用来保存 cur的下个节点
        ListNode temp = null;
        while(null != cur){
            //保存cur的下个节点
            temp = cur.next;
            // 将cur反向指向pre,代表反转
            cur.next = pre;
            // 将pre和cur都向后移动
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
3
class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针,cur每次将next指向到前一个节点pre,pre再记录当前cur,
        //cur最后再继续向后移动直到链表尾,此时的pre记录的就是反转后链表的头链表
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
}
3

Python双链表:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        new_link = None
        while head:
            next = head.next
            head.next = new_link
            new_link = head
            head = next
        return new_link
1

入门菜鸡每次都能看到这个大佬....

1
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return head;
        ListNode temp = head.next;
        head.next = null;
        /*
            temp_2-->3-->4-->5-->null
            1-->null
        */
        while(temp!=null){
            ListNode t = temp.next;  // t_3-->....
            temp.next = head; // 2-->1-->null
            head = temp; // head_2-->1--->null
            temp = t; // temp_3-->...
        }
        return head;
    }
}
1

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        ListNode iter = head;
        while (iter != null) {
            head = iter;
            iter = iter.next;
            
            head.next = preNode;
            preNode = head;
        }

        return preNode;
    }
}
1

遍历链表,使用倒插法插入链表

1
head.next = newHead;
        //更新新链表
        newHead = head;

这里没看懂为什么要这样就是更新链表了