链表题目

1、反转链表

迭代

/**
 * 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) {
        ListNode* pre = nullptr;
        ListNode* next = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ret; 
    }
};

2、k个一组反转链表

ListNode* reverse(ListNode* cur, ListNode* tail){
        ListNode * next = nullptr;
        ListNode * pre = nullptr;
        while(cur != tail)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }



    ListNode* reverseKGroup(ListNode* head, int k){
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* tail = head;
        for(int i=0; i<k; i++)
        {
            if(tail == nullptr) return head;
            tail = tail->next;
        }

        ListNode* dummy = reverse(head, tail);
        head->next = reverseKGroup(tail, k);

        return dummy;
    }