剑指 Offer 24. 反转链表

Offer 24

题目描述：

常规解法

本题的解法很常规，没有其他特别的坑，只需要将链表反转即可。

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/1/26 20:29

 */

/**

 * 题目解析：

 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

 */

public class Offer_24 {

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;

        ListNode current = head;

        while(current != null){

            ListNode temp = current.next;

            current.next = pre;

            pre = current;

            current = temp;

        }

        return pre;

    }

}

递归解法

递归解法需要注意的一个点就是递归的边界，也就是返回条件。
图解

/**

 * 解法二：递归解法，在回溯时需要设置next指针

 */

class Offer_24_1 {

    public ListNode reverseList(ListNode head) {

        return dfs(head, null);

    }

    ListNode dfs(ListNode current, ListNode pre){

        if(current == null)

            return pre;//这里返回的有点难以理解，这里其实是达到原始链表尾部就返回最后的那个元素。这个元素作为新链表的头指针。

        ListNode result = dfs(current.next, current);

        current.next = pre;

        return result;

    }

}

巴特西

剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表

Offer 24

常规解法

递归解法

最新文章

热门文章