leetcode 25. Reverse Nodes in k-Group-蒲公英云

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

这个题的意思就是给定一个链表，按照k个元素为一组，然后把每一组做反序处理。

处理的思路也很简单，首先把链表分割成k个元素的一个子链表，然后对每一个子链表做反序处理，对于不足k个元素的最后一组，不做任何处理。

对于本题难点在于反序链表，我这里给出了两种方案，一种是头部插入法实现反序，这个是把元素不断地插入到头部，空间复杂度是O(1)，这就是本题的考核要点；另一种方法就是使用栈，不过这额外会消耗空间，空间复杂度是O(n)。

代码如下：

import java.util.Stack;
/* class ListNode 
 {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
 }*/
/*
 * 这个问题就是链表分割证k个元素的小组，针对每一个小组做反序处理，不足k个的保持原有顺序
 * 
 * 那么问题就简单了，直接分成按照k个元素为一组，然后针对每组做反序处理
 * 
 * 
 * */
public class Solution 
{
      public ListNode reverseKGroup(ListNode head, int k)
     {
          //特殊情况，特殊处理
          if(head==null || k<=1)
              return head;
          ListNode finalHead=new ListNode(-1);
          finalHead.next=head;
          ListNode iter=finalHead.next,begin=finalHead.next,fa=finalHead;
          int count=0;
          while(iter!=null)
          {
              count++;
              if(count==k)
              {
                  //切割的k个元素的子链表的end.next设置为null，便于处理
                  ListNode end=iter;
                  iter=iter.next;
                  end.next=null;
                  ListNode reverHead=reverseListByStack(begin);
                  //连接链表，fa是上一个子链表的end结点
                  fa.next=reverHead;
                    /*因为是反序结点，所以begin反序之后就是end结点
                     *  这里我们之所以让reverseList返回一个头结点
                     *  是因为我们反转链表的时候设置了一个头结点
                     *  */                  
                  end=begin;
                  end.next=iter;
                  //重新设置所有结点
                  fa=end;
                  begin=end.next;
                  count=0;
              }else 
                  iter=iter.next;
          }
        return finalHead.next;
    }
     /*
      * 使用头插法反序链表
      * */
    public ListNode reverseList(ListNode a) 
    {
        ListNode head=new ListNode(-1);
        head.next=a;
        //last结点其实是不变化的
        //last结点是指的是now的父节点
        ListNode last=head.next,now=last.next;
        while(now!=null)
        {
            //last指向下一个代处理的now结点
            last.next=now.next;
            //插入到head的后面
            now.next=head.next;
            head.next=now;            
            //移动now结点
            now=last.next;
        }
        return head.next;
    }
   /*
    * 借助栈来实现反序链表,不过需要非空间
    * */
   public ListNode reverseListByStack(ListNode a) 
   {
       Stack<ListNode> stack=new Stack<>();
        ListNode head=new ListNode(-1);
        head.next=a;
        ListNode iter=head.next;
        while(iter!=null)
        {
            stack.push(iter);
            iter=iter.next;
        }
        iter=head;
        while(stack.isEmpty()==false)
        {
            iter.next=stack.pop();
            iter=iter.next;
        }
        iter.next=null; 
        return head.next;
    }
}

下面是C++的做法，就是做一个链表分割，然后逆序链表即可。

代码如下：

#include <iostream>
using namespace std;
/*
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class Solution 
{
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if (head == NULL || head->next == NULL || k<=1)
            return head;
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        ListNode* i = newHead->next;
        ListNode* fa = newHead;
        ListNode* begin = newHead->next;
        int count = 0;
        while (i != NULL)
        {
            count++;
            if (count == k)
            {
                ListNode* end = i;
                i = i->next;
                end->next = NULL;
                ListNode* tmpHead = reverse(begin);
                fa->next = tmpHead;
                begin->next = i;
                fa = begin;
                begin = fa->next;
                count = 0;
            }
            else
                i = i->next;
        }
        return newHead->next;
    }
    ListNode* reverse(ListNode* head)
    {
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        ListNode* fa = newHead->next;
        ListNode* now = fa->next;
        while (now != NULL)
        {
            fa->next = now->next;
            now->next = newHead->next;
            newHead->next = now;
            now = fa->next;
        }
        return newHead->next;
    }
};