题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
using System; using System.Collections.Generic; /* public class ListNode { public int val; public ListNode next; public ListNode (int x) { val = x; } } */ class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { // write code here var temp=head; int i=0; while(temp!=null){ temp=temp.next; i++; } int times=i/k; if(times<1) return head; ListNode ans,nextKNode; ListNode fakeHead=new ListNode(-1); ans=fakeHead; for(int ii=0;ii<times;ii++) { var tail=head; var last=reverseToN(head,k, out nextKNode); fakeHead.next=last; head=nextKNode; fakeHead=tail; } return ans.next; } public ListNode reverseToN(ListNode head,int N,out ListNode successor) { if(N==1) { successor=head.next; return head; } ListNode last=reverseToN(head.next, N-1, out successor); head.next.next=head; head.next=successor; return last; } }主要分两步,首先是子函数,翻转前N个节点, 因此通过遍历得到链表长度后,就可以算出需要遍历的次数,这样避免最后几个不足K个时的麻烦。注意不足一次翻转时,要判断。 在翻转过程中,每k个翻一次,注意收尾链接,翻转前的head会变成最后一个也是连接下k个节点的节点!