本文主要是介绍LeetCode [链表] 206. Reverse Linked List （C++和Python实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
206. Reverse Linked List [难度：简单]
【题目】
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
【解题C++】
iteratively or recursively 来，积累英语词汇了~ 迭代和递归。话说这个居然归类为简单orz，大概是我在模拟方面比较笨蛋，我一直认为逆转链表是很难的部分了......
迭代有很多种实现方法，如下的就是在遍历链表的同时，让结点一个个掉头指向新结点，这个过程要更新新结点和头结点的指向，最后返回新结点就好啦。（ps:这个代码非常顶真，实在不懂也方便记忆）
/*** 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 *newL = NULL,*tmp = NULL;if(head==NULL) return head;//遍历链表 while(head){//记录下一个要遍历的结点 tmp = head->next;//当前结点指向新结点 head->next = newL;//更新新结点指向 newL = head;//更新要遍历的结点指向head = tmp;}return newL;}
};递归的核心是把问题的规模缩小，再调用函数一层层返回（栈的思想），最后还得加个终止条件。
/*** 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 *p1,*p2;//前者是空链表的判断，后者是边界条件 if(head==NULL||head->next==NULL)return head;p1 = head; //记录当前结点a0 p2 = head->next; //记录下一结点a1 head = reverseList(p2); //返回a1~an逆转后的头结点 p2->next = p1; //用上面逆转后的尾结点指向原来的头结点 p1->next = NULL; //原来的头结点逆转后作为尾结点，next域置空 return head; }
};【解题Python】
思路同C++。
# 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:newL = tmp = Nonewhile head:tmp = head.nexthead.next = newLnewL = headhead = tmpreturn newL
# 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:p1 = p2 = headif head is None or head.next is None:return headp1 = headp2 = head.nexthead = self.reverseList(p2)p2.next = p1p1.next = Nonereturn head这篇关于LeetCode [链表] 206. Reverse Linked List （C++和Python实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
