java算法OJ（2）链表
目录
1.前言
2.正文
2.1合并俩个有序链表
2.1.1题目描述
2.1.2示例
2.1.3代码
2.2俩数相加
2.2.1题目描述
2.2.2示例
2.2.3代码
2.3分割链表
2.3.1题目描述
2.3.2示例
2.3.3代码
3.小结
1.前言
哈喽大家好吖，今天来对先前学习的链表进行巩固，做几道算法题，如果大家有更加优良的解法欢迎大家多多交流哦。
2.正文
2.1合并俩个有序链表
2.1.1题目描述
2.1.2示例
2.1.3代码
这道题主要还是考察了对链表的基本运用，大体思路如下：
- 分别创建四个节点用于完成对题意的实现，最终是将俩个链表合成一个完整链表
- head头节点用于记录俩个链表的头节点下value的最小值的那个头节点
- cur1节点用于记录head头节点下一个节点
- cur2节点用于记录另一条链表的头节点
- pre节点用于实时更新最新节点
- 接下来就该对题意实现了，本质操作是将节点插入链表与断开链表
- 先判断特殊情况是否存在空链表的情况，直接return即可
- 接着开始判断cur1节点与cur2节点下value值谁大谁小，若谁小就将其接入该链表，并将其对应的cur节点值更新
- pre节点向后更新一位
- 最后再将俩条链表中剩余的最后一个节点接上，return 即可
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if(head1 == null||head2 == null){
return head1 == null ? head2 : head1;
}
ListNode head = head1.val >= head2.val ? head2 : head1;
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 ? cur2 : cur1;
return head;
}
}2.2俩数相加
2.2.1题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
2.2.2示例
2.2.3代码
这道题是通过俩条链表来实现值的相加，既可以在原本的链表上进行处理，也可以通过额外创建一条链表的方式进行处理，根据个人习惯进行选择。下面是具体思路：
- ans为新链表储存答案使用，cur实时更新最新节点，carry用于处理进位。
- 循环跳出条件为俩条链表均为空
- sum变量记录每位的总加和，value用于记录每位本身存储的值
- 处理sum加和时要注意判断链表是否为空，还有处理加和carry。
- 处理加和将其创建新节点并接入。
- 循环最后将俩条链表状态更新。
- 加到最后时要额外处理是否出现进位的情况，若出现再接入，最后return
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = null ,cur = null;
int carry = 0;//记录进位
while(l1 != null||l2 != null){
int sum = 0;//记录总数
int value = 0;//记录存储每个位数值
sum = (l1 == null? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
value = sum % 10;
carry = sum / 10;
if(ans == null){
ans = new ListNode(value);
cur = ans;
}
else{
cur.next = new ListNode(value);
cur = cur.next;
}
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (carry == 1) {
cur.next = new ListNode(1);
}
return ans;
}
}2.3分割链表
2.3.1题目描述
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
2.3.2示例
2.3.3代码
这道题整体思路就是将其分成俩段链表来看待，插入到前后俩侧的条件就是判断与x值的大小关系，具体思路如下：
- 创建四个节点用于记录前后俩对首尾。
- next节点用于记录并保存原链表的下个节点
- 进入循环后先以防止在分区过程中出现循环引用。
- 根据与x大小判断来决定接到前侧还是后侧，记得更新节点
- 最后再判断左侧是否均为空，若为空仅返回右侧
- 若不为空，节点连接后返回左侧头。
public static ListNode partition(ListNode head, int x) {
ListNode leftHead = null, leftTail = null;
ListNode rightHead = null, rightTail = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = null;
if(head.val < x){
if(leftHead == null){
leftHead = head;
}
else{
leftTail.next = head;
}
leftTail = head;
}
else{
if(rightHead == null){
rightHead = head;
}
else{
rightTail.next = head;
}
rightTail= head;
}
head = next;
}
if(leftHead == null){
return rightHead;
}
leftTail.next = rightHead;
return leftHead;
}3.小结
今天的分享到这里就结束了，喜欢的小伙伴别忘了点赞与关注，也欢迎大家多多支持我哦。