[数据结构与算法]七月十四号算法题

代码如下：

package Suanfa;

public class Test1 {
public static void main(String[] args) {
	ListNode head=new ListNode(1);
	ListNode a=new ListNode(2);
	ListNode b=new ListNode(3);
	ListNode c=new ListNode(4);
	head.next=a;
	a.next=b;
	b.next=c;    //链表构造完成
	
	head=reverseKGroup(head,2);
	
	System.out.println(head);
}

 /*单链表进行反转*/
public static ListNode reverse(ListNode head) {   
	if (head == null) {
		return head;
	}
	ListNode pre = head; // 上一个节点
	ListNode cur = head.next; // 这个表示的头节点的下一个节点
	ListNode temp; // 临时节点，用于保存当前节点的指针域

	while (cur != null) {
		temp = cur.next; // 储存当前的节点的下一个节点，防止链表断裂
		cur.next = pre; // 改变节点的转向，指向当前节点的前一个节点
		pre = cur; // pre指向当前节点
		cur = temp; // cur变成下一个节点
	}

	head.next = null;
	return pre;
}

/*链表中每k个一组进行反转*/
public static ListNode reverseKGroup (ListNode head, int k) {   
	if (head == null||head.next==null||k==1) { //如果头节点为空或者只有一个节点，k的值为1的时候，就不要进行反转了
		return head;
	}
	
	ListNode res=new ListNode(0);  //用res作为这个链表的头节点
	res.next=head;
	
	int length=0;   //用length来记录链表的长度
	
	ListNode pre=res,cur=head,temp=null; //反转链表需要用到的变量
	
	while(head!=null) {   //得到链表的长度
		length++;
		head=head.next;
	}
	
	//使用分段的方法将该链表进行反转,求出有多少组要进行反转
	for(int i=0;i<length/k;i++) {
		for(int j=1;j<k;j++) {     //这种方法很巧妙，如果采用单链表的方式去反转，不知道什么时停止，这时候需要计数,这段代码很值钱
			temp=cur.next;
			cur.next=temp.next;
			temp.next=pre.next;
			pre.next=temp;         //进行链表反转的时候，可以用手写的形式，记录指针的移动情况
		}
		pre=cur;
		cur=cur.next;
	}
	return res.next;
}


}

关于如何进行组内链表的反转，思想如下：