Leetcode 206. 反转链表-526互联

初次写代码时，被边界条件各种ban，总是忽略，遂放弃，以下整理出一些评论区大佬边界条件不明显或不需要边界条件的解法。边界条件繁琐的代码不要背，否则笔试各种ban。

比较经典的是下面这种写法，有点抽象,根本思想是有三个指针：

第一个指针在反转段前一个节点固定；

第二个指针是当初的第一个需要反转的节点，每次循环向右移动一个，最后被移动到反转段的尾部；

第三个指针是需要第二个指针当前所指的下一个指针，被搬运到第一个指针的指向节点的后面。

/**
 * 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:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        for(int i = 1; i < left; i ++ ){
            pre = pre->next;//此时pre在left的左边
        }
        head = pre->next;
        for(int i = left; i < right; i ++ ){
            ListNode *nex = head->next;
            head->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
            //从pre->...->head->nex，变成pre->next->...->head
        }
        return dummy->next;

    }
};

第二种方法非常妙。里面没有改变指针的指向关系，而是改变了节点的值，每一次循环都将当前遍历到节点的值交换到反转段的末尾。

/**
 * 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:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        int idx = right - left;
        ListNode *p = head;
        int pos = 1;
        while(pos < left){
            p = p->next;
            ++ pos;
        }

        while(idx > 0){
            ListNode *q = p;
            for(int i = 0; i < idx; i ++ ){
                int tmp = q->val;
                q->val = q->next->val;
                q->next->val = tmp;
                q = q->next;
            }
            idx --;
        }
        return head;
    }
};