[LeetCode] 链表反转相关题目

暂时接触到LeetCode上与链表反转相关的题目一共有3道，在这篇博文里面总结一下。首先要讲一下我一开始思考的误区：链表的反转，不是改变节点的位置，而是改变每一个节点next指针的指向。

下面直接看看LeetCode上的题目：

206. Reverse Linked List

这是一道最基本的链表反转题目。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *p = head;
        ListNode *q = head->next;
        head->next = NULL;
        while (q) {
            ListNode *r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        return p;
    }
};

其实就是不断地将当前访问到的位置的next指针指向它前面的指针，这是最基本的操作了。

92. Reverse Linked List II

这道题目规定了要进行反转的位置区间，比上一题加大了难度。我们要先添加一个头指针，指向head节点（最后返回头指针的next即可）；然后一直往后访问，一直到要反转的节点的前一位停下来。

我们要记录下两个节点的位置：开始反转位置的节点的前一位、开始反转位置的节点。因为在反转后，开始反转的节点的前一个节点的next指针要指向反转的最后一个节点，开始反转的节点的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) {
        if (m == n) return head;
        ListNode *cur = new ListNode(0);
        cur->next = head;
        ListNode *copy = cur;
        for (int i = 0; i < m - 1; i++) {
            cur = cur->next;
        }
        ListNode *temp1 = cur, *temp2 = cur->next;
        cur = cur->next;
        ListNode *p = cur, *q = cur->next;
        for (int i = m; i < n; i++) {
            ListNode *r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        temp1->next = p;
        temp2->next = q;
        return copy->next; 
    }
};

234. Palindrome Linked List

这一题要求在O(n)的时间复杂度和O(1)的空间复杂度下，判断一个链表是否回文链表。

我们可以利用一快一慢两个指针同时前进，当快指针到链表的末尾（即不能往后走）时，慢指针就走到序列中间。（这里有一点值得注意，就是无论节点个数是奇数还是偶数，此时从慢指针指向的节点的后一个节点开始反转就可以了）。反转后，对链表的前半部分和后半部分逐个比较即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *copy = head;
        if (head == NULL || head->next == NULL) return true;
        ListNode * slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = slow->next;
        ListNode *p = slow;
        ListNode *q = slow->next;
        slow->next = NULL;
        while (q) {
            ListNode *r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        while (p) {
            if (p->val != copy->val) {
                return false;
            }
            p = p->next;
            copy = copy->next;
        }
        return true;
    }
};