赞
踩
用三个指针解决,curr用于遍历链表,next是curr得后一个结点的指针,prev是curr的前一个结点的指针。
三个指针初始化:
prev初始化为nullptr
next初始化为nullptr
curr初始化为pHead即链表头结点
思路:curr指向当前结点,负责把当前结点的next指针从指向下一个结点改变为指向上一个结点,为了将整个链表翻转,curr必须遍历每一个结点,并将其指针域改为指向上一个结点。next指针用于在curr改变其指针域指向之前先记录下curr的下一个结点,如果没有next指针记录的话,直接把curr的next指向上一个结点会导致链表断了,即找不到了下一个结点,这样curr就没办法遍历链表了。prev永远指向curr的上一个结点,这也是为什么prev初始化为nullptr,因为首元结点上边已经没有结点了。
因此循环体的逻辑是:
进入循环体的时候
prev正指向curr的上一个结点
用next先记录下curr的下一个结点
将curr的指针域指向prev指向的结点,即curr得上一个结点,这个时候curr指向的结点将会是下次循环中的“上一个”结点
令prev等于curr,即记录下当前结点,即下一次循环的上一个结点
令curr=next,遍历链表中下一个结点
返回值:
因为我们是用curr作为循环条件的,最后一次遍历的时候curr指向nullptr,而prev正指向curr的上一个结点,即反转后链表的首元节点,因此返回prev。
- #include <bits/stdc++.h>
- using namespace std;
-
-
- typedef struct ListNode{
- int val;
- ListNode *next;
- ListNode(int x):val(x),next(NULL){}
- }ListNode;
-
- ListNode* ReverseList(ListNode* head){
- ListNode *prev = NULL;
- ListNode *next = NULL;
- ListNode *cur = head;
-
- while(cur){ // cur用来遍历链表,当cur等于NULL的时候说明最后一个链表也已经翻转过了
- next = cur->next; // 在把当前结点指针转换方向之前,一定要先把指针域备份一下,不然就找不到需要翻转的下一个结点了
- cur->next = prev; // 上一句已经记录了下一个结点的指针,所以可以放心把当前结点指针域翻转,指向上一个结点
- prev = cur; // 对于下一个结点来说,当前结点就是就是它的上一个结点,prev之中记录上一个结点的指针
- cur = next; // 可以翻转下一个结点的指针域了
- }
-
- return prev; // while循环结束的时候,cur指向NULL,即最后一个结点的下一个,那么prev指向的就是最后一个结点,也就是翻转后链表的头结点
- }
-
- int PrintList(ListNode *head){
- while(head != NULL){
- printf("%d ", head->val);
- head = head->next;
- }
- printf("\n");
- return 0;
- }
-
- int main(){
- ListNode node0(0);
- ListNode node1(1);
- ListNode node2(2);
- ListNode node3(3);
-
- ListNode *head = &node0;
- node0.next = &node1;
- node1.next = &node2;
- node2.next = &node3;
- node3.next = NULL;
-
- PrintList(head);
- head = ReverseList(head);
- PrintList(head);
- return 0;
-
-
-
- }

- /**
- * 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:
- // head是一组链表的首元节点,head_next是下一组链表的首元节点
- // 该函数翻转一组k个节点
- ListNode *reverse(ListNode *head, ListNode *head_next){
- ListNode *prev = nullptr;
- ListNode *next = nullptr;
- ListNode *curr = head;
- while(curr != head_next){
- next = curr->next;
- curr->next = prev;
- prev = curr;
- curr = next;
- }
- return prev;
-
- }
- ListNode* reverseKGroup(ListNode* head, int k) {
- ListNode *head_next = head;
- for(int i = 0; i < k; ++i){ // 注意这里滑动k次,因此循环完毕curr指向第k+1个节点,即下一组节点的首元节点
- if(head_next == nullptr) return head;
- head_next = head_next->next;
- }
-
- ListNode *new_head = reverse(head, head_next);
- head->next = reverseKGroup(head_next, k); // head是第一组节点翻转以后的最后一个节点,负责和下边的翻转链表连接起来
- return new_head;
-
-
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。