本文共 6283 字，大约阅读时间需要 20 分钟。

题目：有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K==3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。给定一个单链表的头指针head,同时给定K值，返回逆序后的链表的头指针。

思路：这里的所谓逆序是对现有顺序的逆排序，不是指降序排序，即将k个结点的部分链表进行反转，反转链表在前面LB2中已经做过了，要反转一个链表，可以使用栈，思路很方便，但是需要额外的空间复杂度，最优解是使用空间复杂度为O(1)的解决方案：即总是保留连续的3个结点ppre，pcur，pnext；将pcur.next设置为ppre，然后将ppre，pcur，pnext全部向下移动一个结点即可。即反转K个结点是容易的。

关键是反转了K个结点之后，要将它与前面的已有链表连接起来，即将k个结点的前一个结点pleft与链表的尾结点pend连接起来，然后将链表头结点pstart与k个结点的下一个结点pright连接起来，从而完成链表中局部K个结点的反转。

对于原始链表来说，需要不断隔离出K个结点，对其进行逆序然后再连接到原始链表上面，总是需要保留k个结点之前的结点pleft以及k个结点之后的结点pright。

特殊地：

对于K=0,1时不需要逆序，直接返回原来链表的头结点head即可；

对于第一组的k个结点，反转后的head变成pend，最终返回的是pend，pstart与下一组k个结点的第一个结点pstart进行连接。

代码①：如果不单独将逆序放在一个方法中（即进行方法内联）public class KInverse {	public ListNode inverse(ListNode head, int k) {		// 特殊的输入		if (head == null)  return null;		if (k < 2)   return head;		// 找出k个结点，需要用到4个工具点		ListNode pleft = null;		ListNode pstart = head;		ListNode pright = null;		ListNode pend = null;		// 遍历链表，每得到k个结点进行一次逆序排序操作		ListNode pcur = head;		int count = 1;		while (pcur != null) {			if (count == k) {				// 如果没有反转直接后面返回head，只有对于第一组反转即pend==null需要				// 改变头结点head为pcur，之后都不用改变head，即只有对第一组要修改头结点			//常识：这里使用三目运算优先级是先三目运算得到返回值再赋值：head = pend == null ? pcur : head				head = (pend == null ? pcur : head);			//这里pend是空间位置上的k个结点的最后结点，遍历顺序是321，反转指针后按顺序是123				pend = pcur;				pright = pcur.next;			// 链表的反转问题：设置3个结点（已知pleft，pstart，pright，pend进行反转）				ListNode ppre = pstart;				ListNode pcur2 = ppre.next;				ListNode pnext = null;				while (pcur2 != pright) {					pnext = pcur2.next;					pcur2.next = ppre;					ppre = pcur2;					pcur2 = pnext;				}// 连接到原链表，特殊的，对于第一组即pleft==null时，左端不需要连接；反转好k个指针后关键是将其连接到原来的链表上面，这里需要小心；如果是第一次反转，即pleft为null时，不需要指定pleft.next = ppre//ppre是当前遍历的k个结点中的最后结点，也是逆序后k个结点开始的结点。				if (pleft != null)  pleft.next = ppre;  //pstart是k个结点空间上的第一个结点，即321中的1，也是逆序后的k个结点中的最后一个结点，他要与之后的结点连接 				pstart.next = pright;				// 每次反转后需要重新设置pstart和pleft				pleft = pstart;				pstart = pleft.next;//完成k个结点的逆序后，将count置为0,然后再找之后的k个结点				count = 0;// 此时pcur向下移动到第k+1个结点而不是pcur.next，因为pcur已经逆向，对于pcur=1，他的pcur.next=2而不是6				pcur = pright;			} else {				pcur = pcur.next;			}			count++;		}		return head;	}}

代码②：如果将进行逆序的方法单独提取出来形成一个方法inverseKNode，那么在已知pleft，pstart，pright，pend的情况下如果要对这段链表逆序，需要在调用方法时传入这4个参数，在方法中显然会对pleft，pstart，pright，pend进行修改，关键是理解在方法inverseKNode()中对输入对象的修改是否会真实地对调用位置的pleft，pstart，pright，pend产生变化，这里需要对Java引用传递的深入理解：

pleft，pstart，pright，pend这些字符本身其实是变量符号而已，是存放在栈中的引用指针，他们的值才是存放在堆中的对象，对于变量其实就可以当做是对象实体本身。于是，当pleft，pstart，pright，pend传入给方法inverseKNode之后，相当于方法中的形参pleft,pstart,pend,pright也指向了属性pleft,pstart,pend,pright指向的对象，即他们虽然名称相同，但是是两个变量，指针，批次没有关系，但是他们指向的对象是同一个。于是，当在方法inverseKNode对pstart.next=pright;修改时形参pstart指向的对象与外部pstart变量指向的还是同一个对象，因此在外部pstart还是可以访问到原来的对象，只是对象next值变化了；而在pleft=pstart;pstart=pleft.next修改时形参pleft，pstart指向了不同的对象，即与外部的pleft，pstart指向的不是同一个对象，所以这里对pleft，pstart的修改不会导致外部变量pleft，pstart对应对象的变化，所以在本方法调用后他们的pleft，pstart指向的对象与方法未调用前的值是一样的，即方法没有起效。

public class KInverse {    public ListNode inverse(ListNode head, int k) {//特殊的输入	        if(head==null) return null;	        if(k<2) return head;	        //找出k个结点，需要用到4个工具点	        ListNode pleft=new ListNode(-1);	        ListNode pstart=head;	        ListNode pright=null;	        ListNode pend=null;	        //遍历链表，每得到k个结点进行一次逆序排序操作	        ListNode pcur=head;	        int count=1;	        while(pcur!=null){	            if(count==k){//如果没有反转直接后面返回head，只有对于第一组反转即pend==null需要改变头结点head位pcur，之后都不用改变head	             head=(pend==null? pcur:head);	             pend=pcur;	        		pright=pcur.next;	        		//调用逆序方法对这k个结点排序并连接到原链表上面	        		HashMap
   
    hashMap= inverseKNode(pleft,pstart,pend,pright);	        		pleft=hashMap.get("pleft");	        		pstart=hashMap.get("pstart");	                count=0;//此时pcur向下移动到第k+1个结点	                pcur=pright;	            }else{	            	pcur=pcur.next;	            }	            count++;	      }  	        return head;	    }//对于给定的pstart到pend这几个结点，且已知其前面的结点pleft和后面的结点pright，对结点逆序并且连接到pleft和pright之间	    public HashMap
    
      inverseKNode(ListNode pleft,ListNode pstart,ListNode pend,ListNode pright){	        //链表的反转问题：设置3个结点	    	ListNode ppre=pstart; 	        ListNode pcur2=ppre.next; 	        ListNode pnext=null; 	        while(pcur2!=pright){ 	            pnext=pcur2.next; 	            pcur2.next=ppre; 	            ppre=pcur2; 	            pcur2=pnext; 	        } 	        //连接到原链表，特殊的，对于第一组即pleft==null时，左端不需要连接 	        if(pleft!=null) pleft.next=ppre;//形参pstart指向的对象与外部pstart变量指向的还是同一个对象，因此在外部pstart还是可以访问到原来的对象，只是对象next值变化了。 	        pstart.next=pright;				 	        //一次反转后需要重新设置pstart和pleft//形参pleft，pstart指向了不同的对象，即与外部的pleft，pstart指向的不是同一个对象，所以这里对pleft，pstart的修改不会导致外部变量pleft，pstart对应对象的变化，所以在本方法调用后他们的pleft，pstart指向的对象与方法未调用前的值是一样的，即方法没有起效。 	        pleft=pstart; 	        pstart=pleft.next;            //小心常识：方法调用时传入对象即对象逃逸时如何返回需要的处理后的对象 	        HashMap
     
       hashMap=new HashMap<>(); 	        hashMap.put("pleft", pleft); 	        hashMap.put("pstart", pstart); 	        return hashMap;	    }}类比：这种调用方法是可以的，原因如上面所说。public class KInverse {    public ListNode inverse(ListNode head, int K) {        if (K < 2) {            return head;        }        ListNode cur = head;        ListNode start = null;        ListNode pre = null;        ListNode next = null;        int count = 1;        while (cur != null) {            next = cur.next;            if (count == K) {                start = pre == null ? head : pre.next;                head = pre == null ? cur : head;                resign(pre, start, cur, next);                pre = start;                count = 0;            }            count++;            cur = next;        }        return head;    }     public void resign(ListNode left, ListNode start, ListNode end,            ListNode right) {        ListNode pre = start;        ListNode cur = start.next;        ListNode next = null;        while (cur != right) {            next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }        if (left != null) {            left.next = end;			//只是修改对象的属性，对象还是原来的那个对象        }        start.next = right;    }}