【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“将单链表的每K个节点之间逆序”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每K个节点之间逆序,如果最后不够K个节点一组,则不调整最后几个节点。
例如:
链表:1->2->3->4->5->6->7->8->NULL,K = 3.
调整后为:3->2->1->6->5->4->7->8->NULL。其中7、8不调整,因为不够一组。
【思路】:
解法一:使用栈,每K个清空栈来进行逆序。
解法二:需要保存即将逆序的K个节点的前一个节点pre和后一个节点next
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:list_reverse.cpp
3 *作者:
4 *摘要:将单链表的每K个节点之间逆序
5 */
6
7 #include <iostream>
8 #include <stack>
9
10 using namespace std;
11
12 class Node
13 {
14 public:
15 Node(int data)
16 {
17 value = data;
18 next = NULL;
19 }
20 public:
21 int value;
22 Node *next;
23 };
24
25 Node* resign1(stack<Node*> &s,Node *left,Node *right)
26 {
27 Node *cur = s.top();
28 s.pop();
29 if(NULL != left)
30 left->next = cur;
31 Node *next = NULL;
32 while(!s.empty())
33 {
34 next = s.top();
35 s.pop();
36 cur->next = next; //反转
37 cur = next;
38 }
39 cur->next = right;
40 return cur;
41 }
42
43 Node* reverseKNodes1(Node *head,int K)
44 {
45 if(K < 2)
46 return head;
47 stack<Node*> s;
48 Node *newHead(head),*cur(head),*pre(NULL),*next(NULL);
49 while(NULL != cur)
50 {
51 next = cur->next;
52 s.push(cur);
53 if(s.size() == K)
54 {
55 pre = resign1(s,pre,next);
56 newHead = newHead == head ? cur : newHead;
57 }
58 cur = next;
59 }
60 return newHead;
61 }
62
63 void resign2(Node *left,Node *start,Node *end,Node* right)
64 {
65 Node *pre = start;
66 Node *cur = start->next;
67 Node *next = NULL;
68 while(cur != right)
69 {
70 next = cur->next;
71 cur->next = pre;
72 pre = cur;
73 cur = next;
74 }
75 if(NULL != left)
76 left->next = end;
77 start->next = right;
78 }
79
80 Node* reverseKNodes2(Node *head,int K)
81 {
82 if(2 > K)
83 return head;
84 Node *cur(head),*start(NULL),*pre(NULL),*next(NULL);
85 int count = 1;
86 while(NULL != cur)
87 {
88 next = cur->next;
89 if(count == K)
90 {
91 start = pre == NULL ? head : pre->next;
92 head = pre == NULL ? cur : head; //第一次发生变化的时候确定head
93 resign2(pre,start,cur,next);
94 pre = start;
95 count = 0;
96 }
97 count++;
98 cur = next;
99 }
100 return head;
101 }
102
103 void printList(Node *head)
104 {
105 while(NULL != head)
106 {
107 cout << head->value << " ";
108 head = head->next;
109 }
110 cout << endl;
111 }
112
113 int main()
114 {
115 Node *head = NULL;
116 Node *ptr = NULL;
117
118 for(int i =1;i<9;i++)//构造链表
119 {
120 if(NULL == head)
121 {
122 head = new Node(i);
123 ptr = head;
124 continue;
125 }
126 ptr->next = new Node(i);
127 ptr = ptr->next;
128 }
129 cout << "Before reverse:" << endl;
130 printList(head);
131 cout << "First reverse:" << endl;
132 head = reverseKNodes1(head,3);
133 printList(head);
134 cout << "Second reverse:" << endl;
135 head = reverseKNodes2(head,3);
136 printList(head);
137 return 0;
138 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5386008.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231957
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!