k链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→

// 分段翻转，可以多次调用reverse，然后组合起来
struct LinkedListNode
{
    int data;
    LinkedListNode *next;
    LinkedListNode(int i = 0){data = i; next = NULL;}
};

LinkedListNode* reverse(LinkedListNode* header, int k)
{
    LinkedListNode* end = header;
    int i = k;
    while ( --i )
    {
        end = end->next;
        if ( end == NULL )
        {
            return header;
        }
    }

    LinkedListNode* save = end->next;
    LinkedListNode* p1 = header;
    LinkedListNode* p2 = header->next;
    i = k;
    while ( --i )
    {
        LinkedListNode* temp = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = temp;
    }
    header->next = reverse(save, k);
    return end;
}

int main()
{
    LinkedListNode *n1 = new LinkedListNode(1);
    LinkedListNode *p = n1;
    for ( int i = 2; i < 10; ++i )
    {
        p->next = new LinkedListNode(i);
        p = p->next;
    }
    p = n1;
    while ( p != NULL )
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;

    p = reverse(n1, 4);
    while ( p != NULL )
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;

    return 0;
}

public class Solution{
    public LinkedNode reverseK(LinkedNode head, int k) {
            if(head == null || head.next == null) return head;       
            LiknedNode tail = head;
            for(int i = 0; i< k; i++) {
                if(tail == null) return head;
                tail = tail.next;
            }
            LinkedNode resHead = reverse(head, tail);
            head.next = reverseK(tail, k);
            
            return resHead;
        }

    public LinkedNode reverse(LinkedNode head, LinkedNode tail) {
            LinkedNode pre = null;
            LinkedNode next;
            while(head != tail) {
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
    }
}

package test;

import java.util.ArrayList;
import java.util.List;

public class test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");
        list.add("6");
        System.out.println(reverseList(list, 2));
    }

    public static List<String> reverseList(List<String> list, int k) {
        if (k > 0) {
             // 翻转次数
            int reverseTimes = list.size() / k;
            for (int times = 0; times < reverseTimes; times++) {
                 // 每一段的最后插入到最前，倒数第二插入到第二，以此类推
                for (int index = 0; index < k - 1; index++) {
                    list.add(times * k + index, list.get((times + 1) * k - 1));
                     // 移除已经移动到前面的元素
                    list.remove((times + 1) * k);
                }
            }
        }
        return list;
    }
}

class LinkNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
class Solution:
    def reverse(self,head,tail):
        pre=tail.next
        cur=head
        while pre!=tail:
            a=cur.next
            cur.next=pre
            pre=cur
            cur=a
        return tail,head
    def reverseKGroup(self,head,k):
        node=LinkNode(0)
        node.next=head
        pre=node
        while head:
            tail=pre
            for i in range(k):
            #while k:
                tail=tail.next
                if not tail:
                    return node.next
                #k-=1
            a=tail.next
            head,tail=self.reverse(head,tail)
            pre.next=head
            tail.next=a
            pre=tail
            head=pre.next
        return node.next
    def list2Link(self,nums):
        head=LinkNode(nums[0])
        p=head
        for i in range(1,len(nums)):
            p.next=LinkNode(nums[i])
            p=p.next
        return head

if __name__=='__main__':
    nums=list(map(int,input().split()))
    k=int(input())
    SP=Solution()
    head=SP.list2Link(nums)
    print(SP.reverseKGroup(head,k).val)

public class Solution{
    public ListNode reverseList(ListNode head, int k){
        if(head==null){
            return head;
        }
        int num = 0;
        int length = getLength(head);
        int reverse = length/k;
        if(length<k){
            return head;
        }
        ListNode[] result = new ListNode[reverse+1];
        int count=0;
        ListNode temp = head;
        for(int i=0;i<reverse;){
            count++;
            ListNode next = temp.next;
            temp.next = result[i];
            result[i] = temp;
            temp = next;
            if(count % k == 0){
                i++;
            }
            if(count==reverse*k){
                result[i] = temp;
                break;
            }
        }
        for(int i=0;i<=result.length-2;i++){
            ListNode temp = result[i];
            while(temp!=null&&temp.next!=null){
                temp = temp.next;
            }
            temp.next = result[i+1];
        }
         
        return result[0];
    }
     
    public int getLength(ListNode head){
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            count++;
            temp = temp.next;
        }
        return count;
    }
}
 
class ListNode{
    int val;
    ListNode next;
    public ListNode(){
         
    }
    public ListNode(int val){
        this.val = val;
    }
}

package test;



class Node<Item>{
	Item item;
	Node next;
}

public class TestOne {
	public static void main(String[] args){
		Node<Integer> first=new Node<Integer>();
		Node<Integer> second=new Node<Integer>();
		Node<Integer> third=new Node<Integer>();
		Node<Integer> four=new Node<Integer>();
		Node<Integer> five=new Node<Integer>();
		first.item=1;
		second.item=2;
		third.item=3;
		four.item=4;
		five.item=5;
		
		first.next=second;
		second.next=third;
		third.next=four;
		four.next=five;
		
		Node<Integer> head=reverse(first,1);
		
		for(;head!=null;head=head.next){
			System.out.println(head.item);
		}
	}
	
	public static Node<Integer> reverse(Node<Integer> first,int k){
		if(first==null){
			return null;
		}
		int count=0;
		Node<Integer> last=first;
		Node<Integer> reverseNode=null;
		
		while(count<k&&first!=null){
			Node<Integer> second=first.next;
			first.next=reverseNode;
			
			reverseNode=first;
			first=second;
			count++;
		}
		if(first!=null){
			last.next=first;
		}
		
		return reverseNode;
	}
}

}LNode,*LinkList;

//逆序初始化
int CreatList_L(LinkList &L,int n)
{
 L=(LinkList)malloc(sizeof(LNode));
 L->next=NULL;
 LinkList p;
 for(int i=n;i>0;i--)
 {
  p=(LinkList)malloc(sizeof(LNode));
  if(!p) return OVERFLOW;
  p->next=L->next; L->next=p;
  scanf("%d",&p->data);
 }
 return OK;

}

//顺序初始化
int CreatList_L_2(LinkList &L,int n)
{
 LinkList p,q;
 L=(LinkList)malloc(sizeof(LNode));
 L->next=NULL;
 q=L;
 for(int i=0;i<n;i++)
 {
  p=(LinkList)malloc(sizeof(LNode));
  if(!p) return OVERFLOW;  
  q->next=p;
  //scanf("%d\n",&p->data);     //一定要&
  std::cin>>p->data;
  q=p;
  //free(p);
 }
 q->next=NULL;
 return OK;
}

///第i个元素前插入值为e的结点
int InsertList_L(LinkList &L,int i,ElemType e)
{
 LinkList p,q;
 p=L;
 int j=0;
 while(p&&j<i-1)
 {
  p=p->next;j++;
 }
 if(!p||j>i-1) return ERROR;
 q=(LinkList)malloc(sizeof(LNode));
 if(!q) return OVERFLOW;
 q->next=p->next;
 p->next=q;
 q->data=e;
 return OK;
}

//删除第i个元素，并用e返回数据域
int DeleteList_L(LinkList &L,int i,ElemType &e)
{
 LinkList p,q;
 p=L;
 int j=0;
 while(p&&j<i-1)
 {
  //q=p;
  p=p->next;
  j++;
 }
 if(!p||j>i-1) return ERROR;
 q=p->next;
 p->next=q->next;
 e=q->data;
 free(q);
 return OK;
}

int PrintfList_L(LinkList &L)
{
 LinkList p;
 p=L->next;
 while(p)
 {
  printf("%d\n",p->data);
  p=p->next;
 }
 return OK;
}

//在L中取第index个元素
int GetList_L_e(LinkList &L,int index,LinkList &p)
{
 LinkList q;
 q=L;
 int j=0;
 while(p&&j<index)
 {
  q=q->next;
  j++;
  if(!p||j>index) return ERROR;
 }
 p=q;
 return OK;
}

//表示，从第index个元素开始，将index到index+k这k个元素进行翻转
int K_FanZhuan(LinkList &L,int index,int k)
{
 LinkList p;
 int j=index;
 ElemType e;
 if(GetList_L_e(L,index,p))
 {
  while(p->next&&j<index+k-1)   //要判断p是否是尾节点 p->next是否为空 应该是：p->next&&j<index+k-1  不能是： p&&j<index+k-1
  {
   p=p->next;
   j++;
  }

  for(int i=index;i<j;i++)
  {
   DeleteList_L(L,j,e);
   InsertList_L(L,i,e);
  }

  if(p->next->next)  //当index=1，k=4，while出来后，p为指向第四个结点的指针。。。此时应判断第四个结点的指针域是否为NULL ，故而是p->next->next
  {
   index=index+k;
   K_FanZhuan(L,index,k);
  }
 }
 else
 {
  return ERROR;
 }

}

void main()
{
 LinkList L;
 ElemType e;

 ElemType n,k;
 std::cout<<"LinkList元素个数:\n";
 std::cin>>n;

 std::cout<<"请输入 "<<n<<" 个值，初始化LinkList:\n";   //为using namespace std;则要这样使用
 //CreatList_L(L,5);

 CreatList_L_2(L,n);

 //std::cout<<"输入插入的值：";

 //scanf("%d",&e);

 //InsertList_L(L,5,e);

 //std::cout<<"插值后的LinkList：\n";
 //PrintfList_L(L);

 //std::cout<<"删除第一个元素,并打印删除的值:\n";
 //DeleteList_L(L,1,e);

 //std::cout<<"删除值为:\n";
 //printf("%d\n",e);

 //std::cout<<"删除后的LinkList：\n";
 //PrintfList_L(L);
 ////getchar();
 //system("pause");

 //K翻转
 std::cout<<"L打印：\n";
 PrintfList_L(L);

 std::cout<<"输入k值:\n";
 std::cin>>k;

 K_FanZhuan(L,1,k);

 std::cout<<"k翻转后L打印：\n";
 PrintfList_L(L);
 system("pause");
}

public class LinkList {

	public static void main(String[] args) {
		List<Integer> lst = new LinkedList<>();
		int k = 4;
		for (int i = 1; i < 7; i++)
			lst.add(i);
		reverse(lst, k);
		for (int i = 0; i < lst.size(); i++) {
			System.out.print(lst.get(i) + " ");
		}
	}

	private static void reverse(List<Integer> lst, int k) {
		int index = 0;
		while (index + k - 1 < lst.size()) {
			for (int i = index, j = index + k - 1; i < j; i++, j--) {
				int temp = lst.get(i);
				lst.set(i, lst.get(j));
				lst.set(j, temp);
			}
			index = index + k;
		}
	}
}

//在链表类里面实现功能
struct node
{
	T data;
	node* next;
};

template <class T>
class list 
{
private:
        node<T>* m_pHead;
	node<T>* m_pTail;
public:
        void KthReverse(const unsigned int& k);//链表的K反转
        int List_Length();
};

template <class T>
void list<T>::KthReverse(const unsigned int& k)
{
	unsigned int len = List_Length();
	int time = 0;
	if (len < k)
	{
		return;
	}
	else
	{
		time = len / k;
	}

	//链表反转需要定义三个指针，一次性反转
	node<T>* pCur = m_pHead;
	node<T>* pPrev = NULL;
	node<T>* pNext = NULL;

	//pSubHead指向子链的头，pSubTail指向子链的尾
	node<T>* pSubTail = NULL;
	node<T>* pSubHead;       	

	for (int i=0; i<time; i++)
	{
		pSubHead = pCur;

		//step(1):for循环子块完成链表子链的反转
		for (unsigned int j=0; j<k;j++)
		{
			pNext = pCur->next;
			pCur->next = pPrev;
			pPrev = pCur;
			pCur = pNext;
		}
 
		//step(2):反转后，确定下一个子链的头和尾，并将上一个链尾链接到下一个链的头部
		if (i == 0)
		{
			m_pHead = pPrev;
		}

		pSubHead->next = pCur;

		if (pSubTail != NULL)
		{
			pSubTail->next = pPrev;
		}
		pSubTail = pSubHead;		
	}
        //step(3)安全起见，设置正确的尾指针，并将尾的next置为null
	while (pSubTail->next )
	{
		pSubTail = pSubTail->next;
	}
	m_pTail = pSubTail;
	m_pTail->next = NULL;
	
}
template<class T>
int list<T>::List_Length()
{
	node<T>* p1 = m_pHead;
	int k =0;
	while(NULL != p1)
	{
		k++;
		p1 = p1->next;
	}
	return k;
}

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
  };
    ListNode* reverseKGroup(ListNode* head, int k) {
       ListNode* p=head;
	int listlen=0;
	while(p)
	{
		listlen++;
		p=p->next;
	}
	if(listlen<=1||k<=1||k>listlen)return head;
	int count=listlen/k;
	bool IsFirst=true;
	ListNode** NewHead=NULL;
	ListNode** NewEnd=NULL;
	ListNode** End=NULL;
	while(count--)
	{
		if(IsFirst)
		{
			head=ReverseList(head,NewHead,NewEnd,k);
			End=NewEnd;
			IsFirst=false;
		}
		else
		{
			*End=ReverseList(*NewHead,NewHead,NewEnd,k);
		    End=NewEnd;
		}
	}
	if(listlen%k)
	{
		*End=*NewHead;
	}

	return head;
    }
    ListNode* ReverseList(ListNode* pHead,ListNode** & NewHead,ListNode** &NewEnd,int k)
{
	if (pHead==NULL||pHead->next==NULL)
	{
		return pHead;
	}
	ListNode* p=pHead;
	ListNode* q=p->next;
	p->next=NULL;
	NewEnd=& p->next;
	while (--k)
	{
		p=q;
		q=q->next;
		p->next=pHead;
		pHead=p;
	}
	NewHead=&q;
	return pHead;
}

#include"iostream"
using namespace std;
struct node{
	int data;
	node* next;
	node(int i,node* p){data=i;next=p;}
};
void myReverse(node* head,int k){
	if(!head&&k<1)
		return;
	int temp,i;
	node* p1=head;
	node* p2=head;
	while(p1){
			i=1;
			while(i<k&&p2){
		          p2=p2->next;
		          i++;
	        }
			if(i<k)
				return;
			temp=p1->data;
			p1->data=p2->data;
			p2->data=temp;
			p1=p2->next;
		    p2=p1;
		}
}
int _tmain(int argc, _TCHAR* argv[])
{
	node n6(6,0);
	node n5(5,&n6);
	node n4(4,&n5);
	node n3(3,&n4);
    node n2(2,&n3);
    node n1(1,&n2);

	node* p=&n1;
	while(p){
		cout<<p->data;
		p=p->next;
	}
	cout<<endl;
	myReverse(&n1,4);
    p=&n1;
	while(p){
		cout<<p->data;
		p=p->next;
	}
    return 0;  
}

    
    下面是一种递归实现 //返回每一段子链表的头结点
    public static ListNode K_LinkListReverse(ListNode list , int k ){
        if(list == null|| list.next == null || k < 2)
            return  list;
        ListNode newTail = list ;
        ListNode newHead = list ;
        ListNode oldHead = list.next ;
        int currentCount = 1 ;
        while(currentCount != k && oldHead != null){
            newTail.next = oldHead.next;
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = newTail.next;
            currentCount++;
        }
        //与上个新的子链表拼接起来
        newTail.next = K_LinkListReverse(oldHead, k);
        return newHead;
    }
    //节点结构
    public class ListNode {
        public int value;
       public ListNode next ;
    }

public static void reverse2(TNode head, int k) {
 if(null == head) 
    return;

 // 前中后临时变量，
 TNode pre = head;
 TNode cur = head.nextNode;
 TNode next = cur;
 head.nextNode = null;
 // 子链反转前的第一个结点
 TNode firstNode = null;
 // 前一个子链反转前的第一个结点
 TNode preFirstNode = head;

 while(null != cur) { // 子链反转前的第一个结点
     firstNode = next;
     for(int i=0; i<k&& cur!=null; i++) {
         next = cur.nextNode;
         // 到K点，
         if( pre == null || pre.obj==null)
             cur.nextNode = null;
         else
             cur.nextNode = pre;
         pre = cur;
         cur = next;
     }
     // 连接两个子链
     preFirstNode.nextNode = pre;
     preFirstNode = firstNode;
     pre = null;
 } 
 // 最后一个节点的下一个节点为null
 firstNode.nextNode = null;
 }