C++翻转链表

大家好，我是讯享网，很高兴认识大家。

1 题目描述

讯享网

2 解题思路与代码

用三个指针解决，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; }

讯享网

3 扩展------k个一组翻转链表

讯享网/ * 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; } };

1 题目描述

2 解题思路与代码

3 扩展------k个一组翻转链表

相关推荐