刷题——将单链表的每K个节点之间逆序

给定一个单链表的头结点head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点

解1：使用栈辅助，先把所有节点进栈，再出栈实现反向

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 
10 // 解法1： 使用栈辅助
11 class Solution {
12     public ListNode reverseKGroup(ListNode head, int k) {
13         if(k<2)
14             return head;
15         Stack<ListNode> stack = new Stack<ListNode>();
16         ListNode cur = head;
17         ListNode newhead = null;
18         int cnt = 0;
19         
20         while(cur != null){
21             stack.push(cur);
22             cnt = (cnt+1)%k;
23             cur = cur.next;
24         }
25         
26         while(cnt-- != 0){
27             stack.peek().next = newhead;
28             newhead = stack.pop();
29         }
30         
31         while(!stack.isEmpty()){
32             cur=stack.pop();
33             ListNode curhead = cur;
34             cnt = k-1;
35             while(cnt != 0){
36                 cur.next = stack.pop();
37                 cur = cur.next;
38                 cnt --;
39             }
40             cur.next = newhead;
41             newhead = curhead;
42         }
43         return newhead;
44     }
45 }

View Code

解2：不需要栈结构，在原链表中直接调整，难点在于要注意记录每组的head,tail，并将上一组的tail的next指针链接到本组的head，而且第一组要单独处理

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 
10 // 解法2： 不使用辅助栈，在原栈上直接以K个分组，进行逆置
11 class Solution {
12     public ListNode reverseKGroup(ListNode head, int k) {
13         if(k<2 || head==null)
14             return head;
15         
16         ListNode curhead = head;
17         ListNode cur = head;
18         ListNode nexthead = null;
19         ListNode lasttail = null;
20         ListNode newhead = null;
21         
22         int cnt = 0;
23         boolean fstgroup = true;
24         while(curhead != null){
25             // determining group head and tail
26             cnt = 1;
27             cur = curhead;
28             while(cur!=null && cnt != k){
29                 cur = cur.next;
30                 cnt ++;
31             }
32             
33             ListNode curtail = cur;
34             nexthead = (cur!=null && cur.next!=null) ? cur.next : null;
35             
36             if( cur != null){
37                 if(fstgroup)
38                     newhead = cur;
39             }else{
40                 if(fstgroup)
41                     return head;
42                 else{
43                     lasttail.next = curhead;
44                     return newhead;
45                 }
46             }
47             
48             // reverse current group
49             ListNode pre = null;
50             ListNode next = null;
51             cur = curhead;
52             while(cur != nexthead){
53                 next = cur.next;
54                 cur.next = pre;
55                 pre = cur;
56                 cur = next;
57             }
58             
59             if(fstgroup)
60                 lasttail = head;
61             else{
62                 lasttail.next = curtail;
63                 lasttail = curhead;
64             }
65             
66             curhead = nexthead;
67             fstgroup = false;
68             
69         }
70         
71         return newhead;
72     }
73 }

View Code