445. Add Two Numbers II

LeetCode


  1. Add Two Numbers II:题目链接

基本思想：题目要求不能用逆转链表的方法，那么就用栈充当容器相当于逆转了链表，从各位开始算起，模拟手算的过程

方法1

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct {
    struct ListNode * pTop;
}LinkStack;

LinkStack * createStack(){
    LinkStack *pS = (LinkStack *) malloc(sizeof(LinkStack));
    pS->pTop = NULL;
    return pS;
}

void push(LinkStack * pS, int val){
    struct ListNode *pNew = (struct ListNode *) malloc(sizeof(struct ListNode ));
    pNew->val = val;
    pNew->next = pS->pTop;
    pS->pTop = pNew;
}

int pop(LinkStack * pS){
    struct ListNode *pTemp = pS->pTop;
    int popData = pTemp->val;
    pS->pTop = pTemp->next;
    free(pTemp);
    return popData;
}

int emptyStack(LinkStack * pS){
    return NULL == pS->pTop;
}

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    LinkStack *stack_1 = createStack();             // 此栈存放 l1链表
    LinkStack *stack_2 = createStack();             // 此栈存放 l2链表
    LinkStack *stack_sum = createStack();           // 此栈存放结果
    // 建虚拟头结点 指针域记得置NULL
    struct ListNode *dummy = (struct ListNode *) malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode *curNode_1 = l1, *curNode_2 = l2, *pTail = dummy;
    // 将l1中所有节点 入栈 7 2 4 3 入栈变成 3 4 2 7
    while (curNode_1) {
        push(stack_1, curNode_1->val);
        curNode_1 = curNode_1->next;
    }
    // 将l2中所有节点 入栈
    while (curNode_2) {
        push(stack_2, curNode_2->val);
        curNode_2 = curNode_2->next;
    }

    int sum = 0, carry = 0;
    // 两个栈都不为空 则将其栈顶元素 + 进位 入stack_sum栈
    while (!emptyStack(stack_1) && !emptyStack(stack_2)) {
        sum = pop(stack_1) + pop(stack_2) + carry;
        carry = sum / 10;
        push(stack_sum, sum % 10);
    }
    // 如果stack_1不空  stack_2空
    while (!emptyStack(stack_1)) {
        sum = pop(stack_1) + carry;
        carry = sum / 10;
        push(stack_sum, sum % 10);
    }
    // 如果stack_2不空  stack_1空
    while (!emptyStack(stack_2)) {
        sum = pop(stack_2) + carry;
        carry = sum / 10;
        push(stack_sum, sum % 10);
    }
    // 当遍历到最后两个数 相加时 其值 >= 10
    if (carry > 0) {
        push(stack_sum, carry);
    }
    // 将stack_sum中的元素出栈 加入到链表dummy中 从 7 0 8 7变成 7 8 0 7
    while (!emptyStack(stack_sum)){
        struct ListNode *pNew = (struct ListNode *) malloc(sizeof(struct ListNode));
        pNew->val = pop(stack_sum);
        pNew->next = NULL;
        pTail->next = pNew;
        pTail = pNew;
    }
    return dummy->next;
}

方法2：在之前的基础上 优化

  1. 不需要利用stack_sum 直接使用从头部插入节点的建立链表方式
  2. 将两个栈空 一个栈空 最后两个数进位为1 等情况整合起来
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct {
    struct ListNode * pTop;
}LinkStack;

LinkStack * createStack(){
    LinkStack *pS = (LinkStack *) malloc(sizeof(LinkStack));
    pS->pTop = NULL;
    return pS;
}

void push(LinkStack * pS, int val){
    struct ListNode *pNew = (struct ListNode *) malloc(sizeof(struct ListNode ));
    pNew->val = val;
    pNew->next = pS->pTop;
    pS->pTop = pNew;
}

int pop(LinkStack * pS){
    struct ListNode *pTemp = pS->pTop;
    int popData = pTemp->val;
    pS->pTop = pTemp->next;
    free(pTemp);
    return popData;
}

int emptyStack(LinkStack * pS){
    return NULL == pS->pTop;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    LinkStack *stack_1 = createStack();             // 此栈存放 l1链表
    LinkStack *stack_2 = createStack();             // 此栈存放 l2链表
    // 建虚拟头结点 指针域记得置NULL
    struct ListNode *dummy = (struct ListNode *) malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode *curNode_1 = l1, *curNode_2 = l2, *pTail = dummy;
    // 将l1中所有节点 入栈 7 2 4 3 入栈变成 3 4 2 7
    while (curNode_1) {
        push(stack_1, curNode_1->val);
        curNode_1 = curNode_1->next;
    }
    // 将l2中所有节点 入栈
    while (curNode_2) {
        push(stack_2, curNode_2->val);
        curNode_2 = curNode_2->next;
    }

    int sum = 0, carry = 0;
    // 改进： 将两个栈空 一个栈空  最后两个数进位为1 等情况整合起来
    while (!emptyStack(stack_1) || !emptyStack(stack_2) || carry != 0) {
        int val_1 = emptyStack(stack_1) ? 0 : pop(stack_1);
        int val_2 = emptyStack(stack_2) ? 0 : pop(stack_2);
        sum = val_1 + val_2 + carry;
        carry = sum / 10;
        struct ListNode *pNew = (struct ListNode *) malloc(sizeof(struct ListNode));
        pNew->val = sum % 10;
        pNew->next = dummy->next;
        dummy->next = pNew;
    }
    return dummy->next;
}

方法3：利用两个栈 + 头插法的链表

基本思想： 将两个链表分别压入栈中，然后出栈将结果用头插法放到结果链表中

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct {
    struct ListNode * pTop;
}LinkStack;

LinkStack * createStack(){
    LinkStack *pS = (LinkStack *) malloc(sizeof(LinkStack));
    pS->pTop = NULL;
    return pS;
}

void push(LinkStack * pS, int val){
    struct ListNode *pNew = (struct ListNode *) malloc(sizeof(struct ListNode ));
    pNew->val = val;
    pNew->next = pS->pTop;
    pS->pTop = pNew;
}

int pop(LinkStack * pS){
    struct ListNode *pTemp = pS->pTop;
    int popData = pTemp->val;
    pS->pTop = pTemp->next;
    free(pTemp);
    return popData;
}

int emptyStack(LinkStack * pS){
    return NULL == pS->pTop;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    LinkStack * stack1 = createStack();
    LinkStack * stack2 = createStack();
    struct ListNode* head = (struct ListNode* ) malloc (sizeof(struct ListNode));
    head = NULL;
   
    int sum = 0, carry = 0;
    struct ListNode* cur1 = l1, * cur2 = l2;
    
    while (cur1 != NULL) {
        push(stack1, cur1->val);
        cur1 = cur1->next;
         
    }
    
    while (cur2 != NULL) {
        push(stack2, cur2->val);
        cur2 = cur2->next;
    }
    // printf("1------------\n");
    while (emptyStack(stack1) == 0 && emptyStack(stack2) == 0 ) {
        // printf("22222------------\n");
        int top1 = pop(stack1);
        int top2 = pop(stack2);
        sum = top1 + top2 + carry;
        carry = sum / 10;
        struct ListNode* newNode = (struct ListNode* ) malloc (sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = head;
        head = newNode;
    }
    
    while (emptyStack(stack1) == 0 ) {
        int top1 = pop(stack1);
        sum = top1 + carry;
        carry = sum / 10;
        struct ListNode* newNode = (struct ListNode* ) malloc (sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = head;
        head = newNode;
    }
    
     while ( emptyStack(stack2) == 0) {
  
        int top2 = pop(stack2);
        sum = top2 + carry;
        carry = sum / 10;
        struct ListNode* newNode = (struct ListNode* ) malloc (sizeof(struct ListNode));
        newNode->val = sum % 10;
        newNode->next = head;
        head = newNode;
    }
    
    if (carry > 0) {
        struct ListNode* newNode = (struct ListNode* ) malloc (sizeof(struct ListNode));
        newNode->val =carry;
        newNode->next = head;
        head = newNode;
    }
    return head;
}

pS: 源代码链接

本文标题:445. Add Two Numbers II

文章作者:XerDemo

发布时间:2018-10-07, 14:55:38

最后更新:2019-07-11, 10:42:23

原始链接:https://xerdemo.github.io/2018/10/07/445-Add-Two-Numbers-II/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 方法1
  2. 2. 方法2：在之前的基础上 优化
  3. 3. 方法3：利用两个栈 + 头插法的链表
|