LeetCode:Reverse Nodes in k-Group

简介:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, 
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5


每次选取好一个group后,调用翻转链表子函数翻转该group

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class  Solution {
public :
     ListNode *reverseKGroup(ListNode *head, int  k) {
         ListNode tmphead(0);
         ListNode *p = head, *tail = &tmphead; //tail 为当前已经处理完的尾节点
         while (p)
         {
             ListNode *groupHead = p;
             int  i = 1;
             for (i = 1; i < k && p->next != NULL; i++)p = p->next;
             if (i != k){tail->next = groupHead; return  tmphead.next;} //最后不足k个节点
             p = p->next;
             pair<ListNode*, ListNode*>ht = reverseList(groupHead, p);
             tail->next = ht.first;
             tail = ht.second;
         }
         return  tmphead.next;
     }
     //翻转链表,并返回翻转后链表的头结点和尾节点
     pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode *end)
     {
         ListNode *p = head, *newHead = NULL;
         while (p != end)
         {
             ListNode *tmp = p->next;
             p->next = newHead;
             newHead = p;
             p = tmp;
         }
         return  make_pair(newHead, head);
     }
};

 

上面的方法实际上遍历了2遍链表,可以稍加改进在计数k个链表的过程中就开始翻转, 最后部分如果不足k个节点,则还原原来的顺序                                 本文地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class  Solution {
public :
     ListNode *reverseKGroup(ListNode *head, int  k) {
         ListNode tmphead(0);
         ListNode *p = head, *tail = &tmphead; //tail 为当前已经处理完的尾节点
         while (p)
         {
             pair<ListNode*, ListNode*>ht = reverseList(p,k);
             tail->next = ht.first;
             tail = ht.second;
             p = tail->next;
         }
         return  tmphead.next;
     }
     //翻转从head开始的k个链表节点,如果不足k个则不翻转,返回翻转后的这k个节点
     //子链表的head和tail。翻转后的子链表还是和子链表后面的部分相连的。
     pair<ListNode*, ListNode*> reverseList(ListNode* head, int  k)
     {
         ListNode *p = head, *newHead = NULL;
         int  cnt = 0;
         while (p && cnt < k)
         {
             ListNode *tmp = p->next;
             p->next = newHead;
             newHead = p;
             p = tmp;
             cnt++;
         }
         head->next = p; //把翻转后的子链表和子链表后面的部分连起来
         if (cnt == k)
             return  make_pair(newHead, head);
         else  return  reverseList(newHead, cnt); //不足k个,还原原来的顺序
     }
};

 






本文转自tenos博客园博客,原文链接:http://www.cnblogs.com/TenosDoIt/p/3794505.html,如需转载请自行联系原作者

目录
相关文章
Leetcode 24.Swap Nodes in Pairs
 给你一个链表,交换相邻两个节点,例如给你 1->2->3->4,输出2->1->4->3。   我代码里在head之前新增了一个节点newhead,其实是为了少写一些判断head的代码。
39 0
|
索引
LeetCode 345. Reverse Vowels of a String
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
98 0
LeetCode 345. Reverse Vowels of a String
|
机器学习/深度学习 NoSQL
LeetCode 344. Reverse String
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
95 0
LeetCode 344. Reverse String
LeetCode 190. Reverse Bits
颠倒给定的 32 位无符号整数的二进制位。
88 0
LeetCode 190. Reverse Bits
LeetCode 150. Evaluate Reverse Polish Notation
根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
45 0
LeetCode 150. Evaluate Reverse Polish Notation
LeetCode 92. Reverse Linked List II
给定一个链表,反转指定的子序列.
79 0
LeetCode 92. Reverse Linked List II
|
机器学习/深度学习 NoSQL 算法
LeetCode 344. 反转字符串 Reverse String
LeetCode 344. 反转字符串 Reverse String
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List
LeetCode之Reverse String II
LeetCode之Reverse String II
114 0
LeetCode之Reverse String
LeetCode之Reverse String
101 0