剑指 Offer 24. 反转链表

本问题对应的 leetcode 原文链接：剑指 Offer 24. 反转链表

问题描述

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

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码实现

方法一：原地反转
时间复杂度：O(N)
额外空间复杂度 O(1)

class Solution {
    // 原地反转
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode cur = head, pre = null;

        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;

        // 额外空间复杂度=1
    }
}

方法2：递归
时间复杂度：O(N)
额外空间复杂度 O(n)，递归调用需要消耗栈空间

  // 递归
      public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 反转子链表
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return temp;
    }

Python

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head

        # 反转子链表
        temp = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return temp

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 反转子链表
        ListNode* temp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return temp;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    // 反转子链表
    temp := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil

    return temp
}

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }

    let cur = head,
        pre = null;

    while (cur != null) {
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }

    return pre;

    // 额外空间复杂度=1
};

shuaidi永久会员

收藏 海报挣佣金 推广链接