剑指 Offer 24. 反转链表

题目

剑指 Offer 24. 反转链表

题解

递归

1，先递归到链表的尾部：

2，反转尾部，变为头部：

3，以此类推，完成反转：

//Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //寻找递归终止条件
        //1、head指向的节点为null
        //2、head指向的节点的下一个节点为null
        //在这两种情况下，反转之后的结果还是它自己本身
        if (head == null || head.next == null) return head;

        //不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        //因为到最后一个节点的时候，由于当前节点的head的next节点是空，所以会直接返回head
        ListNode cur = reverseList(head.next);

        //比如原链表为 1->2->3->4->5->null
        //5->4
        //第一次执行下面代码的时候，head为4，那么head.next = 5
        //那么head.next.next 就是 5.next，意思就是去设置5的下一个节点
        //等号右侧为head，意思就是设置5的下一个节点是4
        head.next.next = head;

        //head原来的下一节点指向自己，所以head自己本身就不能再指向原来的下一节点了
        head.next = null;
        
        //我们把每次反转后的结果传递给上一层
        return cur;
    }
}

leetcode-cn执行用时：

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.7 MB, 在所有 Java 提交中击败了71.89%的用户

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    //寻找递归终止条件
    //1、head指向的节点为null
    //2、head指向的节点的下一个节点为null
    //在这两种情况下，反转之后的结果还是它自己本身
    if head == nil ||head.Next == nil {
        return head
    }
    //不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
    //因为到最后一个节点的时候，由于当前节点的head的next节点是空，所以会直接返回head
    cur := reverseList(head.Next)
    //比如原链表为 1->2->3->4->5->null
    //5->4
    //第一次执行下面代码的时候，head为4，那么head.next = 5
    //那么head.next.next 就是 5.next，意思就是去设置5的下一个节点
    //等号右侧为head，意思就是设置5的下一个节点是4
    head.Next.Next = head
    //head原来的下一节点指向自己，所以head自己本身就不能再指向原来的下一节点了
    head.Next = nil
    //我们把每次反转后的结果传递给上一层
    return cur
}