LeetCode 每日一题206: 反转链表

LeetCode

提前祝大家春节快乐~

题目

反转一个单链表。

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

---

数据结构定义

C

/**
 * Definition for singly-linked list.
*/
struct ListNode {
     int val;
      struct ListNode *next;
 };

Python

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

---

思路

按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

迭代反转

迭代反转借助两个指针, 主指针用于遍历, 前向指针用于反转.

需要注意的是, 由于Python的独特赋值语句, 在进行指针赋值交换的时候, 一句语句即可实现, 不需要借助临时变量保存待交换的变量, 同时, 利用这个特性也有助于加快程序运行速度, 读者应当熟练这个语法规则. 若觉得Python实现较难理解, 可以先看看C语言的实现.

此时head指针作为主指针移动, p指针记住head指针当前位置, head->next与pre指针实现反转, 迭代中反转的顺序是由前往后.

C实现

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *p = head, *pre = NULL;
    while(p){
        p = head->next;
        head->next = pre;
        pre = head;
        head = p;
    }
    return pre;
}

image.png

Python实现

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p, pre = head, None
        while p:
            pre, pre.next, p = p, pre, p.next
        return pre

---

递归反转

递归中则相反, 反转的顺序是由后往前. 主指针head->next遍历至尾部程序栈依次弹出, 依次反转直到回到第一个指针停止, 返回反转后的链表头指针.

如果你觉得代码比较难理解, 可以参考下面我绘制的图.

递归栈

C实现

struct ListNode* reverseList(struct ListNode* head) {
    if(!head || !head->next)
        return head;
    struct ListNode *p = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return p;
}

image.png

Python实现

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

---

公众号: 程序员的碎碎念