两个单链表生成相加链表

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“两个单链表生成相加链表”这一题目的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

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。