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
公众号: 程序员的碎碎念
