转载请标明出处http://www.cnblogs.com/haozhengfei/p/9e6f4dda3138cf9fab17f996ec85b624.html
链表的K逆序问题
链表的k逆序
第7节 链表的k逆序练习题
有一个单链表，请设计一个算法，使得每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值，返回逆序后的链表的头指针。
Java (javac 1.7)
代码自动补全
1
import java.util.*;
2
3
/*
4
public class ListNode {
5
int val;
6
ListNode next = null;
7
8
ListNode(int val) {
9
this.val = val;
10
}
11
}*/
12
public class KInverse {
13
public ListNode inverse(ListNode head, int k) {
14
if (k < 2) {
15
return head;
16
}
17
ListNode cur = head;//正在遍历的当前节点
18
ListNode start = null;
19
ListNode pre = null;
20
ListNode next = null;//待遍历的下一个节点
21
int count = 1;
22
while (cur != null) {
23
next = cur.next;
24
if (count == k) {//count满足要求开始进行逆序
25
start = pre == null ? head : pre.next;
26
head = pre == null ? cur : head;
27
resign(pre, start, cur, next);
28
pre = start;
29
count = 0;
30
}
31
count++;
32
cur = next;
33
}
34
return head;
35
}
36
public void resign(ListNode left, ListNode start, ListNode end,
37
ListNode right) {
38
ListNode pre = start;
39
ListNode cur = start.next;
40
ListNode next = null;
41
while (cur != right) {
42
next = cur.next;
43
cur.next = pre;
44
pre = cur;
45
cur = next;
46
}
47
if (left != null) {
48
left.next = end;
49
}
50
start.next = right;
51
}
52
}
您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例
答案正确:恭喜！您提交的程序通过了所有的测试用例
运行