核心考点:链表操作,思维缜密程度
输入一个链表,反转链表后,输出新链表的表头。
解析一:(三指针法)
利用三个指针进行链表的反转:
- left,mid,right依次指向第一个结点,第二个结点和第三个结点。
- 让mid指向的结点指向left。
- left,mid,right统一向右移动。
- 反复指向步骤2和步骤3,直到right指向链表表尾,即nullptr。
- 再让mid指向的结点指向left。
- 最后让第一个结点指向空,即nullptr。
注意: 当链表为空或链表当中只有一个结点时,链表无需反转。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if (pHead == nullptr || pHead->next == nullptr) //链表为空或链表只有一个结点,无需反转
return pHead;
ListNode* left = pHead;
ListNode* mid = left->next;
ListNode* right = mid->next;
while (right != nullptr)
{
//mid指向left
mid->next = left;
//left,mid和right统一向右移动
left = mid;
mid = right;
right = right->next;
}
mid->next = left; //mid指向left
pHead->next = nullptr; //第一个结点指向nullptr
return mid; //返回新链表的表头,也就是此时的mid
}
};
解析二:(头插法)
还可以使用头插的方式进行链表的反转,具体过程就是依次取原链表的第一个结点头插到一个空链表当中,当原链表当中的结点全部被取完时,原来的空链表就是反转后的新链表。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if (pHead == nullptr || pHead->next == nullptr) //链表为空或链表只有一个结点,无需反转
return pHead;
ListNode* newHead = nullptr;
while (pHead != nullptr)
{
//从原链表获取第一个结点
ListNode* p = pHead;
pHead = pHead->next;
//将该结点头插到新链表
p->next = newHead;
newHead = p;
}
return newHead; //返回新链表的表头
}
};