25 Reverse Nodes in K Group 每k个一组翻转链表

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

k is 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 of k then 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

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

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

Difficulty: Hard

这道题让我们以每k个为一组进行链表翻转.就是把原来的链表分成若干小段,然后分别对其进行翻转

解法1

用两个函数,一个用于分段,一个用于翻转.在做这种链表翻转的题的时候需要考虑是不是要加一个dummy node,因为翻转时候头结点可能会变化.不过这个dummy结点在使用过后需要释放.我们用pre,next指针分别指向要翻转的子链表的前后位置.

例如:k=3

-1(pre)->1->2->3->4(next)->5

-1->3->2->1(pre)->4(next)->5
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k==1) return head;
        ListNode* dummy = new ListNode(-1);
        ListNode* pre = dummy,*cur = head;
        dummy->next = head;
        int i = 0;
        while(cur)
        {
            i++;
            if (i % k == 0)
            {
                pre = reverseOneGroup(pre,cur->next);
                cur = pre->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        ListNode* res = dummy->next;
        delete dummy;
        dummy = NULL;
        return res;
    }
    
    //-1, 1, 2, 3, 4, 5
    ListNode* reverseOneGroup(ListNode* pre,ListNode*next)
    {
        ListNode* last = pre->next;
        ListNode* cur = last->next;
        //第一次循环 1->3,2->1,-1->2,cur=3
        while(cur != next)
        {
            last->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = last->next;
        }
        return last;
    }
    
};

解法2

当k=2的时候,每段需要交换1次,k=3每段需要交换2两次,会发现每段为k-1次.下面用一个函数完成

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1),*pre = dummy,*cur = pre;
        dummy->next = head;
        int num = 0;
        while (cur = cur->next) num++;
        while (num >= k)
        {
            cur = pre->next;
            for (int i = 1; i < k; i++) {
                ListNode* t = cur->next;
                cur->next = t->next;
                t->next = pre->next;
                pre->next = t;
            }
            pre = cur;
            num -= k;
        }
        ListNode* res = dummy->next;
        delete dummy;
        dummy = NULL;
        return res;
    }
};

解决3

使用递归解决,用head记录每段开始位置,cur记录结束位置的下一个结点,然后调用reverse翻转,得到一个new_head,原来的head编程末尾.这时候继续递归

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur= head;
        for (int i = 0;i < k;i++)
        {
            if (!cur) return head;
            cur = cur->next;
        }
        ListNode* new_head = reverse(head,cur);
        head->next = reverseKGroup(cur,k);
        return new_head;
    }
    
    ListNode* reverse(ListNode* head,ListNode* tail)
    {
        ListNode* pre = tail;
        while(head!=tail)
        {
            ListNode* t = head->next;
            head->next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }
};

参考: http://www.cnblogs.com/grandyang/p/4441324.html

 
comments powered by Disqus