仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

链表减法

发表于 更新于 分类于 ， ，
本文字数： 4.8k 阅读时长 ≈ 4 分钟

【道德经·第二十四章】企者不立，跨者不行；自见者不明；自是者不彰；自伐者无功；自矜者不长。其在道也，曰余食赘形。物或恶之，故有道者不处。

Given two linked lists that represent two large positive numbers. Subtract the smaller number from the larger one and return the difference as a linked list. Note that the input lists may be in any order, but we always need to subtract smaller from the larger ones.
It may be assumed that there are no extra leading zeros in input lists.
文章转载自GeeksForGeeks

示例：

1
2
3
4
5
6
7
8
9
10
11
Input: l1 = 1 -> 0 -> 0 -> NULL,  l2 = 1 -> NULL
Output: 0->9->9->NULL
Explanation: Number represented as 
lists are 100 and 1, so 100 - 1 is 099

Input: l1 = 7-> 8 -> 6 -> NULL,  l2 = 7 -> 8 -> 9 NULL
Output: 3->NULL
Explanation: Number represented as 
lists are 786 and  789, so 789 - 786 is 3, 
as the smaller value is subtracted from 
the larger one.

思路：

  1. Calculate sizes of given two linked lists.
  2. If sizes are not the same, then append zeros in the smaller linked list.
  3. If the size is the same, then follow the below steps:
  • Find the smaller valued linked list.
  • One by one subtract nodes of the smaller-sized linked list from the larger size. Keep track of borrow while subtracting.

代码实现：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
// C++ program to subtract smaller valued list from
// larger valued list and return result as a list.
#include <bits/stdc++.h>
using namespace std;

// A linked List Node
struct Node {
	int data;
	struct Node* next;
};

// A utility which creates Node.
Node* newNode(int data)
{
	Node* temp = new Node;
	temp->data = data;
	temp->next = NULL;
	return temp;
}

/* A utility function to get length
of linked list */
int getLength(Node* Node)
{
	int size = 0;
	while (Node != NULL) {
		Node = Node->next;
		size++;
	}
	return size;
}

/* A Utility that padds zeros in front of the
Node, with the given diff */
Node* paddZeros(Node* sNode, int diff)
{
	if (sNode == NULL)
		return NULL;

	Node* zHead = newNode(0);
	diff--;
	Node* temp = zHead;
	while (diff--) {
		temp->next = newNode(0);
		temp = temp->next;
	}
	temp->next = sNode;
	return zHead;
}

/* Subtract LinkedList Helper is a recursive function,
move till the last Node, and subtract the digits and
create the Node and return the Node. If d1 < d2, we
borrow the number from previous digit. */
Node* subtractLinkedListHelper(Node* l1, Node* l2, bool& borrow)
{
	if (l1 == NULL && l2 == NULL && borrow == 0)
		return NULL;

	Node* previous
		= subtractLinkedListHelper(
			l1 ? l1->next : NULL,
			l2 ? l2->next : NULL, borrow);

	int d1 = l1->data;
	int d2 = l2->data;
	int sub = 0;

	/* if you have given the value to next digit then
	reduce the d1 by 1 */
	if (borrow) {
		d1--;
		borrow = false;
	}

	/* If d1 < d2, then borrow the number from previous digit.
	Add 10 to d1 and set borrow = true; */
	if (d1 < d2) {
		borrow = true;
		d1 = d1 + 10;
	}

	/* subtract the digits */
	sub = d1 - d2;

	/* Create a Node with sub value */
	Node* current = newNode(sub);

	/* Set the Next pointer as Previous */
	current->next = previous;

	return current;
}

/* This API subtracts two linked lists and returns the
linked list which shall have the subtracted result. */
Node* subtractLinkedList(Node* l1, Node* l2)
{
	// Base Case.
	if (l1 == NULL && l2 == NULL)
		return NULL;

	// In either of the case, get the lengths of both
	// Linked list.
	int len1 = getLength(l1);
	int len2 = getLength(l2);

	Node *lNode = NULL, *sNode = NULL;

	Node* temp1 = l1;
	Node* temp2 = l2;

	// If lengths differ, calculate the smaller Node
	// and padd zeros for smaller Node and ensure both
	// larger Node and smaller Node has equal length.
	if (len1 != len2) {
		lNode = len1 > len2 ? l1 : l2;
		sNode = len1 > len2 ? l2 : l1;
		sNode = paddZeros(sNode, abs(len1 - len2));
	}

	else {
		// If both list lengths are equal, then calculate
		// the larger and smaller list. If 5-6-7 & 5-6-8
		// are linked list, then walk through linked list
		// at last Node as 7 < 8, larger Node is 5-6-8
		// and smaller Node is 5-6-7.
		while (l1 && l2) {
			if (l1->data != l2->data) {
				lNode = l1->data > l2->data ? temp1 : temp2;
				sNode = l1->data > l2->data ? temp2 : temp1;
				break;
			}
			l1 = l1->next;
			l2 = l2->next;
		}
	}
	// If both lNode and sNode still have NULL value,
	// then this means that the value of both of the given linked lists
	// is the same and hence we can directly return a node with value 0.
	if(lNode==NULL&&sNode==NULL)
	{
		return newNode(0);
	}
	// After calculating larger and smaller Node, call
	// subtractLinkedListHelper which returns the subtracted
	// linked list.
	bool borrow = false;
	return subtractLinkedListHelper(lNode, sNode, borrow);
}

/* A utility function to print linked list */
void printList(struct Node* Node)
{
	while (Node != NULL) {
		printf("%d ", Node->data);
		Node = Node->next;
	}
	printf("\n");
}

// Driver program to test above functions
int main()
{
	Node* head1 = newNode(1);
	head1->next = newNode(0);
	head1->next->next = newNode(0);

	Node* head2 = newNode(1);

	Node* result = subtractLinkedList(head1, head2);

	printList(result);

	return 0;
}

位我上者，灿烂星空；道德律令，在我心中。