首页 > 代码库 > 算法--链表的K逆序问题
算法--链表的K逆序问题
转载请标明出处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值,返回逆序后的链表的头指针。
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
}
您的代码已保存
答案正确:恭喜!您提交的程序通过了所有的测试用例
答案正确:恭喜!您提交的程序通过了所有的测试用例
算法--链表的K逆序问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。