[剑指 Offer 第 2 版第 24 题] “反转链表”做题记录

第 24 题：输入一个链表，反转链表后，输出链表的所有元素

传送门：AcWing：反转链表，牛客网 online judge 地址。

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

样例：

输入：1->2->3->4->5->NULL

输出：5->4->3->2->1->NULL

分析：这道题同 LeetCode 上一道问题，可以使用“穿针引线”也可以使用递归求解。个人觉得递归的方式比较简单，但是在链表较长的时候，递归效率偏低，因为要使用系统栈。

思路1：递归。

Python 代码：

  # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    # 递归写法：用递归就不用思考穿针引线这种事情了。


    class Solution:
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            # 递归的终止条件一定要写对：考虑结点为空和单结点的情况
            if head is None or head.next is None:
                return head
            next = head.next
            new_head = self.reverseList(next)
            next.next = head
            head.next = None
            return new_head

Java 代码：

  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        // 递归写法要画个图就清楚了
        public ListNode ReverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode next = head.next;
            ListNode newHead = ReverseList(next);
            next.next = head;
            head.next = null;
            return newHead;
        }

    }

思路2：非递归写法，穿针引线。

Python 代码：

  # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    # 穿针引线，可以看到 while 循环体部分的代码是首尾相连的，有些单链表的题目也有这种规律，感觉很神奇
    # 在 Python 中，其实还有更简便的写法，就跟斐波拉契数列一样


    class Solution:
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """

            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/