LeetCode 中等难度 92. 反转链表 II解题思路

92. 反转链表 II

题目：中等难度

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路：
1.基础首先是普通链表反转，也就是需要一个新链表头指针new_head指向新链表的头部，然后从旧链表里找到需要反转的节点利用头插法插入到新链表里。
2.着重点是找到需要反转的节点------按位查找。
3.需要标记旧链表里的四个特殊节点，反转完毕后连接成目标链表。如下图

4.把反转后3里找到的四个节点重新链接即可。

总结:主体框架是按位查找+链表反转+重要位置节点的标记

需要注意的几个点：

1.以上四个指针的初始赋值问题，第一个指针不能直接赋值head。因为如果m等于1时，这个指针的值应为Null。重点需要注意第一个指针是NULL的情况。
2.反转时创建了新的链表，利用头插法把旧链表的头结点插到新链表时，要提前用一个next指针标记旧链表的下一个节点，不然旧链表的头结点断开后就找不到新节点。

附上代码：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution { public:ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode* pre_head=NULL; //反转部分的前一个节点——有可能为空（即m为1的情况）ListNode* new_head=NULL; //反转后的链头ListNode* list_tail=NULL; //反转后的链尾ListNode* result=head; //返回值ListNode* next; //反转时用来标记原链表的指针int len=n-m+1; // 反转的节点的数量// 寻找需要反转的第一个节点while(head&&--m) { pre_head=head; //1.指针跟随head=head->next; //2.指针下移}list_tail=head; //反转部分之前的链头就是反转之后的链尾//实现反转部分 while(head&&(len--)) { next=head->next; //先标记原链表的下一个节点head->next=new_head; //把原链表的第一个节点插入到新链表的头new_head=head; //更新新链表的头结点指针head=next; //更新旧链表的头结点指针}list_tail->next=head;//判断健壮性 --注意pre_head为null的情况if(pre_head) {pre_head->next=new_head;}else{result=new_head;}return result;} };

总结

以上是生活随笔为你收集整理的LeetCode 中等难度 92. 反转链表 II解题思路的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。