LeetCode刷题之链表(持续更新)
程序员文章站
2024-03-16 16:09:40
...
链表数据结构:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
1. 反转链表
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
public class Test1 {
public ListNode reverseList(ListNode head) {
if(head == null) {
return null;
}
ListNode prev = null;
while(head != null) {
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
2. 两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
public class Test2 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) { //先进行形参的判断,提高执行效率
return null;
}
if (l1 == null) { //因为上面判断了l1和l2,所以这里如果l1是null,那么l2必然有值,直接返回l2即可
return l2;
}
if (l2 == null) { //理由同上
return l1;
}
ListNode result = new ListNode(0);
ListNode temp = result;
while (true) {
if (l1 != null) {
temp.val = temp.val + l1.val;
l1 = l1.next;
}
if (l2 != null) {
temp.val = temp.val + l2.val;
l2 = l2.next;
}
temp.next = new ListNode(temp.val / 10);
temp.val = temp.val % 10;
if (l1 == null && l2 == null) {
temp.next = (temp.next.val == 0 ? null : temp.next);
break;
}
temp = temp.next;
}
return result;
}
}
3. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
public class Test3 {
//方法1
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = null;
result = merge(result, l1, l2);
return result;
}
public ListNode merge(ListNode result, ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) {
return null;
}
if(l1 == null && l2 != null) {
return l2;
}
if(l1 != null && l2 == null) {
return l1;
}
if(l1.val > l2.val) {
result = l2;
l2 = l2.next;
} else {
result = l1;
l1 = l1.next;
}
result.next = merge(result.next, l1, l2);
return result;
}
//方法2
public ListNode mergeTwoList(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null) {
return l1 != null ? l1 : l2;
}
ListNode head = l1.val < l2.val ? l1 : l2; //满足条件的链结点
ListNode other = l1.val >= l2.val ? l1 : l2; //不满足条件的链结点
ListNode preHead = head; //当前位置(满足条件)
ListNode preOther = other; //当前位置(不满足条件)
while (preHead != null) {
ListNode next = preHead.next;
if(next != null && next.val > preOther.val) {
preHead.next = preOther;
preOther = next;
}
if(preHead.next == null) {
preHead.next = preOther;
break;
}
preHead = preHead.next;
}
return head;
}
}
上一篇: 随记_求N位数范围内的所有自幂数
下一篇: 1256: 奇数检测