leetcode—_两数相加

发表于 | 分类于 ，

链表是数据结构中比较重要的一个知识点，结合leetcode的第二题-两数相加来看看链表的实现。

一篇文章搞定面试中的链表题目(java实现)

Java实现单链表的插入、删除、计算链表的长度和输出链表

链表顾名思义就是一种带链子的表，一环扣一环。每一个环节都可分成两个部分，一部分是数据，一部分是指向下一个环节的指针。

如果要定义一个链表环节可以这么做

1
2
3
4
5
6
7
8
9
10
public class ListNode {
	
	int data;//data就是每个环节所存储的数据
	ListNode next = null;//next用来储存下一个环节的地址
	
	public  ListNode(int data) {
		this.data = data;
	}	

}

当我们使用的时候，可以这样

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
public class Main {
	
	public static void main(String[] args) {
		
		Main myMain = new Main();
		
		
		ListNode l1 = null;
		l1 = myMain.insertNode(1, l1);
		myMain.insertNode(2, l1);
		myMain.insertNode(3, l1);
		
		ListNode l2 = null;
		l2 = myMain.insertNode(1, l2);
		myMain.insertNode(2, l2);
		myMain.insertNode(3, l2);
		
		ListNode node = myMain.addTowNode(l1, l2);
		myMain.printNodelist(node);
	}
	

//这个方法是用来循环打印数据
	public static void printNodelist(ListNode listNode) {
		ListNode node = listNode;
		while(node != null) {
			System.out.print(node.data+" ");
			node = node.next;
		}
		
		System.out.println();
	}

	

	
	//往链表中插入数据
	public ListNode insertNode(int data, ListNode node) {
		
		ListNode head = new ListNode(data);
		if(node == null) {
			node = head;
			return node;
		}
		
		ListNode temp = node;
		while(temp.next != null) {
			temp = temp.next;
		}
		
		temp.next = head;
		return node;
	}
	
    //将两个链表的每个数据进行相加
	public ListNode addTowNode(ListNode l1, ListNode l2) {
		ListNode p = l1;
		ListNode q = l2;
		ListNode head = null;
		int carry = 0;
		while(p != null || q != null) {
			int x = (p != null)?p.data:0;
			int y = (q != null)?q.data:0;
			int sum = x + y;
			head = insertNode(sum % 10, head);
			carry = sum / 10;
			
			if(p != null) {
				p = p.next;
			}
			
			if (q != null) {
				q = q.next;
			}
		}
		
		if(carry > 0) {
			head.next = new ListNode(carry);
		}
		
		return head;
	}
}

在leetcode中的题目是这样要求的：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

看看我这修改了无数遍的答案

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
//    public static ListNode insertNode(int data, ListNode node) {
		
// 		ListNode head = new ListNode(data);
// 		if(node == null) {
// 			node = head;
// 			return node;
// 		}
		
// 		ListNode temp = node;
// 		while(temp.next != null) {
// 			temp = temp.next;
// 		}
		
// 		temp.next = head;
// 		return node;
// 	}
	
	public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode p = l1;
		ListNode q = l2;
		ListNode head = new ListNode(0);//这里使用了哑节点，不需要判断空值情况
         ListNode curr = head;
		int carry = 0;
		while(p != null || q != null) {
			int x = (p != null)?p.val:0;
			int y = (q != null)?q.val:0;
			int sum = x + y + carry;
			// head = insertNode(sum % 10, head);
            
           
//             if(curr == null){
//                 curr = new ListNode(sum % 10);
//             }else{
//                 curr.next = new ListNode(sum % 10);
//                 curr = curr.next;
//             }
           curr.next = new ListNode(sum % 10);
            curr = curr.next;
            
            
			carry = sum / 10;
			
			if(p != null) {
				p = p.next;
			}
			
			if (q != null) {
				q = q.next;
			}
		}
		
		if(carry > 0) {
			curr.next = new ListNode(carry);
		}
		
		return head.next;
	}
}

看看真正的哑结点的用法

链表 - 哑节点

定义结构体

1
2
3
4
struct ListNode {
    int val;
    struct ListNode *next;
};

如果引入了哑节点的，函数就可以得到简化，

在调用addNode()函数之前，我们先定义哑节点

1
2
3
struct ListNode *dummyNode= (struct ListNode*) malloc( sizeof(struct ListNode)  );
dummyNode->val = null;
dummyNode->next = null;

使用

1
2
3
4
5
6
ListNode *addNode( ListNode *dummyNode, int num){	// 函数返回的是尾节点
    struct ListNode *new = (struct ListNode*) malloc( sizeof(struct ListNode) * num );
    /* 此处不再需要处理头节点为空的情况，因为dummyNode一定非空 */
    dummyNode->next = new;
    return new;
}
-------------本文结束感谢您的阅读-------------