反转从位置 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; } };