两个单链表生成相加链表

发布于 — 2019 年 10 月 15 日
#链表

题目

假设链表中每一个节点的值都在0~9之间, 那么链表整体就可以代表一个整数

例如: 9→3→7, 可以代表整数937

给定两个这种链表的头节点, 请生成代表两个整数相加值的结果链表.

例如: 链表1为9→3→7. 链表2为6→3. 最终生成的结果链表为1→0→0→0

题解

有两种方式

  1. 借助栈
  2. 将链表反转后再进行相加

借助栈

 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


public Node addLists1(Node head1, Node head2) {
		Stack<Integer> s1 = new Stack<>();
		Stack<Integer> s2 = new Stack<>();
		while (head1 != null) {
			s1.push(head1.value);
			head1 = head1.next;
		}
		while (head2 != null) {
			s2.push(head2.value);
			head2 = head2.next;
		}
		Node node = null;
		Node pre = null;
		int ca = 0;
		while (!s1.isEmpty() || !s2.isEmpty()) {
			int n1 = s1.isEmpty() ? 0 : s1.pop();
			int n2 = s2.isEmpty() ? 0 : s2.pop();
			int n = n1 + n2 + ca;
			ca = n / 10;
			pre = node;
			node = new Node(n % 10);
			node.next = pre;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;
		}
		return node;
	}

反转链表

 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

public Node addLists2(Node head1, Node head2) {
		head1 = reverseList(head1);
		head2 = reverseList(head2);

		Node c1 = head1, c2 = head2;
		Node node = null, pre = null;
		int ca = 0;
		while (c1 != null || c2 != null) {
			int n1 = c1 != null ? c1.value : 0;
			int n2 = c2 != null ? c2.value : 0;
			int n = n1 + n2 + ca;
			ca = n / 10;
			pre = node;
			node = new Node(n % 10);
			node.next = pre;
			c1 = c1 != null ? c1.next : null;
			c2 = c2 != null ? c2.next : null;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;
		}
		// 将head1, head2再反转回去
		return node;
	}

	private Node reverseList(Node head) {
		Node pre = null;
		while (head != null) {
			Node next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

相关题目

两数相加