网站建设要准备什么在线工具

题目链接

剑指 Offer II 024. 反转链表 easy

题目描述

给定单链表的头节点 head，请反转链表，并返回反转后的链表的头节点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 $[0,5000]$
• $-5000\le Node.val\le 5000$

分析：模拟

我们用 cur指向 当前结点 ，用 pre指向当前结点的 前驱节点 ， 用 nextNode指向当前结点的 后继结点。

让cur的下一个结点指向 pre。接着再让 pre指向当前结点 cur，让cur指向 nextNode。

一直这样操作，直到 cur指向 null，此时的 pre指向的就是反转后的链表头节点，直接返回即可。

时间复杂度： $O(n)$

C++代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *pre = nullptr , *cur = head;while(cur != nullptr){ListNode *nextNode = cur->next;cur->next = pre;pre = cur;cur = nextNode;}return pre;}
};

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: ListNode) -> ListNode:pre , cur = None , headwhile cur != None:nextNode = cur.nextcur.next = prepre = curcur = nextNodereturn pre