【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“两个单链表生成相加链表”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
假设链表中每一个节点的值都在 0~9 之间,那么链表整体就可以代表一个整数。
例如:9->3->7,可以代表整数937。
给定两个这种链表的头节点 head1 和 head2,请生成代表两个整数相加值的结果链表。
例如:链表 1 为9->3->7,链表 2 为 6->3,最后生成新的结果链表为1->0->0->0。
【思路】:
解法一:使用栈
解法二:将两个链表逆序后再进行相加操作
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:list_add.cpp
3 *作者:
4 *摘要:两个链表生成相加链表
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* addList1(Node *head1,Node *head2)
26 {
27 stack<int> s1;
28 stack<int> s2;
29 //分别入栈
30 while(NULL != head1)
31 {
32 s1.push(head1->value);
33 head1 = head1->next;
34 }
35 while(NULL != head2)
36 {
37 s2.push(head2->value);
38 head2 = head2->next;
39 }
40
41 int ca(0),n1(0),n2(0),n(0);
42 Node *node = NULL;
43 Node *pre = NULL;
44 while(!s1.empty() || !s2.empty())
45 {
46 if(s1.empty())
47 {
48 n1 = 0;
49 }
50 else
51 {
52 n1 = s1.top();
53 s1.pop();
54 }
55 if(s2.empty())
56 {
57 n2 = 0;
58 }
59 else
60 {
61 n2 = s2.top();
62 s2.pop();
63 }
64
65 n = n1 + n2 + ca;
66 pre = node;
67 node = new Node(n % 10);
68 node->next = pre;
69 ca = n / 10;
70 }
71 if(1 == ca)
72 {
73 pre = node;
74 node = new Node(1);
75 node->next = pre;
76 }
77 return node;
78 }
79
80 //链表反转
81 Node* reverseList(Node *head)
82 {
83 Node *pre = NULL;
84 Node *next = NULL;
85 while(NULL != head)
86 {
87 next = head->next;
88 head->next = pre;
89 pre = head;
90 head = next;
91 }
92 return pre;
93 }
94
95 Node* addList2(Node *head1,Node *head2)
96 {
97 head1 = reverseList(head1);
98 head2 = reverseList(head2);
99 int ca(0),n1(0),n2(0),n(0);
100
101 Node *p1 = head1;
102 Node *p2 = head2;
103 Node *node = NULL;
104 Node *pre = NULL;
105 while(NULL != p1 || NULL != p2)
106 {
107 n1 = NULL != p1 ? p1->value : 0;
108 n2 = NULL != p2 ? p2->value : 0;
109 n = n1 + n2 + ca;
110 pre = node;
111 node = new Node(n % 10);
112 node->next = pre;
113 ca = n / 10;
114 p1 = NULL != p1 ? p1->next : NULL;
115 p2 = NULL != p2 ? p2->next : NULL;
116 }
117 if(1 == ca)
118 {
119 pre = node;
120 node = new Node(1);
121 node->next = pre;
122 }
123 reverseList(head1);
124 reverseList(head2);
125
126 return node;
127 }
128
129 //打印链表
130 void printList(Node *head)
131 {
132 while(NULL != head)
133 {
134 cout << head->value << " " ;
135 head = head->next;
136 }
137 cout << endl;
138 }
139
140 int main()
141 {
142 Node *head1 = NULL;
143 Node *head2 = NULL;
144 Node *ptr1 = NULL;
145 Node *ptr2 = NULL;
146 for(int i =1;i<6;i++)//构造链表
147 {
148 if(NULL == head1 || NULL == head2)
149 {
150 head1 = new Node(i);
151 head1->next = NULL;
152 ptr1 = head1;
153 head2 = new Node(10-i);
154 head2->next = NULL;
155 ptr2 = head2;
156 continue;
157 }
158 ptr1->next = new Node(i);
159 ptr1 = ptr1->next;
160 ptr1->next = NULL;
161 ptr2->next = new Node(10-i);
162 ptr2 = ptr2->next;
163 ptr2->next = NULL;
164 }
165 cout << "The datum of the fir list are :" << endl;
166 printList(head1);
167 cout << "The datum of the sec list are :" << endl;
168 printList(head2);
169
170 cout << "After adding list1 and list2 through using stack:" << endl;
171 ptr1 = addList1(head1,head2);
172 printList(ptr1);
173 cout << "After adding list1 and list2 through reverse list:" << endl;
174 ptr2 = addList2(head1,head2);
175 printList(ptr2);
176 return 0;
177 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5377469.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231757
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!