快捷搜索:

LT简单题206-反转链表

题目描述:

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

示例 1:

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

示例 2:

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

方法一:两个指针(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* p = nullptr;

ListNode* q = nullptr;

while(head){

q = head->next;

head->next = p;

p = head;

head = q;

}

return p;

}

};

时间复杂度:O(n),空间复杂度:O(1)

经验分享 程序员 微信小程序 职场和发展