206. Reverse Linked List

Reverse a singly linked list.

S: linked list basic operation

三个节点一组进行操作: before->head->next => before<-head<-next

    ListNode* reverseList(ListNode* head) {
        ListNode* before = NULL;
        ListNode* next;
        while(head){
            next = head->next;
            head->next = before;
            before = head;
            head = next;
        }
        return before;
    }

92. 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.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

S: linked list basic operation

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int count = 1;
        ListNode dummy(0);
        ListNode* before = NULL, *next, *tail, *start = &dummy;
        dummy.next = head;
        while(head && count <= n){
            next = head->next;
            if(count == m-1) start = head;
            else if(count == m){
                tail = head;
                before = head;
            } 
            else if(count > m){
                next = head->next;
                head->next = before;
                before = head;
            }
            head = next;
            count++;
        }
        start->next = before;
        tail->next = head;
        return dummy.next;
    }

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked listkat a time and return its modified list.

kis a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple ofkthen left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list:1->2->3->4->5

Fork= 2, you should return:2->1->4->3->5

Fork= 3, you should return:3->2->1->4->5

S: recursion + dummy node

记录reverse片段的前一节点，用dummy node避免corner case

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) {
            return head;
        }
        ListNode dummy(-1);
        dummy.next = head;
        reverseK(&dummy, k);
        return dummy.next;
    }

    void reverseK(ListNode* preNode, int k) {
        if (!preNode || !preNode->next) {
            return;
        }
        ListNode* node = preNode->next;
        int count = 0;
        while(node && count < k) {
            node = node->next;
            count++;
        }
        if (count < k) return;
        ListNode *newEnd = preNode->next;
        ListNode *pre = preNode->next;
        ListNode *cur = pre->next;
        ListNode *next;
        while (cur != node) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        preNode->next = pre;
        newEnd->next = cur;
        reverseK(newEnd, k);
    }
};

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

S: slow,fast pointer + reverse linked list

翻转后半list然后一一比较

    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        ListNode *slow = head, *fast = head, *rev;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        if(fast) rev = revList(slow->next);
        else rev = revList(slow);
        while(rev){
            if(rev->val != head->val) return false;
            rev = rev->next;
            head = head->next;
        }
        return true;
    }

    ListNode* revList(ListNode* head){
        ListNode* before = NULL;
        ListNode* next;
        while(head){
            next = head->next;
            head->next = before;
            before = head;
            head = next;
        }
        return before;
    }