瀚钦科技网站建设,公司查名网站,做网站的必要,seo臻系统题目链接 剑指 Offer II 024. 反转链表 easy 题目描述
给定单链表的头节点 head#xff0c;请反转链表#xff0c;并返回反转后的链表的头节点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1] 示例 2#xff1a; 输入#xff1a;h…题目链接 剑指 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][0, 5000][0,5000]−5000≤Node.val≤5000-5000 \leq Node.val \leq 5000−5000≤Node.val≤5000
分析模拟
我们用 cur指向 当前结点 用 pre指向当前结点的 前驱节点 用 nextNode指向当前结点的 后继结点。 让cur的下一个结点指向 pre。接着再让 pre指向当前结点 cur让cur指向 nextNode。 一直这样操作直到 cur指向 null此时的 pre指向的就是反转后的链表头节点直接返回即可。
时间复杂度 O(n)O(n)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, val0, nextNone):
# 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
