LeetCode—Reverse Linked List II指定位置翻转单链表

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

这里是通过指定位置进行链表翻转，其实链表的翻转可以有很多方法，不外乎就是一些指针位置的相互修改

这里的方法很简单

1 初始化一个begin,cur（end）节点记录 需要翻转的节点的前一个节点和当前节点，同时end就是翻转后对应的最后一个点

2 从开始需要翻转的下一个节点开始

2       3        4

pPre Cur    pNex       每次只需要cur->next = pPre,然后3个节点依次向后移动，因为有pNext所以不怕链表断裂

1      2    <-    3   <-     4  <-    5       6

be    en                                 pre     cur   pnext

最后将begin->pPre,  end->Cur就可以了

/**
 * 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) {
//<可能出现的一些特殊情况：m = 1表示为头结点，n = length为尾节点，m = n不进行翻转，这三种情况都要考虑到
//<这里采用的方法就是将不进行翻转的部分的节点先保存下来，需要翻转的先翻转，然后再连接上
        if (head == NULL)
            return NULL;

        ListNode *begin = NULL; //<因为是记录m节点的前一个节点，所以一开始应该赋值为NULL
        ListNode *cur = head;
        for(int i = 0; i < m - 1; i++)
        {
            begin = cur;
            cur = cur->next;
        }

        ListNode *end = cur; //<翻转过后这个点就是最后一个节点了
        ListNode *pPre = cur; //  pre cur pNext 三个之间进行交换
        cur = cur->next;
        for(int i = m + 1; i <= n; i++) //<n这里直接走到了n已经是翻转链表的下一个位置了
        {
            ListNode *pNext = cur->next;
            cur->next = pPre;
            pPre = cur;
            cur = pNext; //<通过cur得到下一个节点，画图明显
        }

        end->next = cur;
        if (begin)
            begin->next = pPre;
        else
            head = pPre;
        
        return head;
    }
};