|
反转链表用三指针
三指针解法分两种情况
第一种情况没有头节点，头节点包括了第一个值
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//*by myself(三指针)
if (head == nullptr || head->next == nullptr) { //链表为空，或者len=1返回head
return head;
}
ListNode* first = head; //头指针
ListNode* last = head->next; //尾指针
ListNode* prev = last->next; //尾指针指向节点的下一个节点指针（目的是为了在last->next = first之后，保存原来的last->next，从而继续遍历原来的链表）
first->next = nullptr; //首先设置头指针next=nullptr(也是反转后的尾指针)
while (prev != nullptr) { //prev指针遍历整个链表
last->next = first; //反转
first = last; //反转之后，三个指针同时向后移动
last = prev;
prev = prev->next;
}
last->next = first; //因为循环结束时，最后一个节点还未反转，所以这里补上
return last; //返回源链表的最后一个节点(也是反转后链表的头节点)
}
};
第二种情况是包括了头节点的情况
template<class T>
bool LinkList<T>::Invert(void){
if(head==NULL){
cerr<<"逆置的单链表不存在"<<endl;//如果头节点不存在的话不能进行逆置了，说明头节点分配失败
return false;
}
linkNode<T>* first,*current = head->next;
//定义多两个指针
while(current){
//当前节点不为空，将原链表的首结点更新到最新处
first = current;
//当前节点更新为当前节点的后继
current = current->next;
//原链表的首结点更新为新链表的头结点的后继
first->next = head->next;
//新链表的头结点的后继更新为原链表的首结点
first = head->next;
}
//已经逆置了当前链表，返回true
return true;
}
|