基础结构
· val: 节点存储数值 · next：指向下一个节点的指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
合并两个有序链表（升序）
思路
处理边界：若有一个链表为空，直接返回另一个
确定新链表头：取值较小的作为头结点
用pre作为已排序部分的最后一个节点
双指针遍历cur1和cur2，逐一比较并连接到pre.next
循环结束后，若有剩余节点，直接挂到末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) {
return head1 == null ? head2 : head1;
}
ListNode head = head1.val <= head2.val ? head1 : head2;
ListNode cur1 = head.next;
ListNode cur2 = head == head1 ? head2 : head1;
ListNode pre = head;
while (cur1 != null && cur2 != null) {
if (cur1.val <= cur2.val) {
pre.next = cur1;
cur1 = cur1.next;
} else {
pre.next = cur2;
cur2 = cur2.next;
}
pre = pre.next;
}
pre.next = cur1 != null ? cur1 : cur2;
return head;
}
两个链表相加
思路
初始化结果链表 ans 和指针 cur。
循环条件：只要 l1 或 l2 不为空。
sum = l1.val + l2.val + carry，取个位数作为当前节点值，十位数作为进位。
第一次循环时新建结果链表头结点；后续追加新节点。
循环结束后，如果 carry==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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = null;
ListNode cur = null;
int carry = 0;
for (int sum, val; l1 != null || l2 != null;
l1 = (l1 == null ? null : l1.next),
l2 = (l2 == null ? null : l2.next)) {
sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
val = sum % 10;
carry = sum / 10;
if (ans == null) {
ans = new ListNode(val);
cur = ans;
} else {
cur.next = new ListNode(val);
cur = cur.next;
}
}
if (carry == 1) {
cur.next = new ListNode(1);
}
return ans;
}