0 题目描述
leetcode原题链接:反转链表
1 双指针法
- 定义两个指针: pre 和 cur;pre 在前 cur 在后。
- 每次让 pre 的 next 指向 cur,实现一次局部反转
- 局部反转完成之后,pre 和 cur 同时往前移动一个位置
- 循环上述过程,直至 pre 到达链表尾部
Python版本:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = None, head
while pre:
t = pre.next
pre.next = cur
cur = pre
pre = t
return cur
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) {
ListNode *cur, *pre, *t;
cur = NULL;
pre = head;
while(pre)
{
t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
};
2 递归法
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
参考资料
【反转链表】:双指针,递归,妖魔化的双指针