目录
两数相加
-
题目介绍
-
思路分析
-
首先我们需要将题目中的有效信息提取出来:根据题目我们得知两个链表的头节点均不为0；然后每个链表的节点的值域为[0-9],然后将相应节点对应相加得到一个新的链表
-
这样分析过来好像这道题很’简单’,根本对不上题目设定的中等难度。那么这道题的坑在哪呢？这道题本意是利用链表去模拟加法的竖式运算,那么问题来了,根据竖式运算，新的链表的每个节点的值域应该为[0-9]，但原链表节点相加的值不一定就会小于9,也就是说我们要考虑进位的问题.
-
也就是说进制会导致该节点的下一个节点的值增加,那么具体增加多少呢？我们直到在初始节点进行相加时两个节点相加的最大值为18(两个9)。也就是初始节点进位最大进1,然后看第二个节点,在上一位进1的基础上相加的最大值为19,然后再进1,因此我们得知节点相加进位的最大值为1。
-
现在我们得到了进位的具体关系,然后我们依次遍历两个链表,将相加的值的个位存入新节点(n%10)，然后根据是否进位来判断下一个节点相加时是否要额外加1。但问题又来了,假如两个链表的长度不一样呢？这样的话你遍历的结束条件为两个节点均不空好像不太行。
-
因此我们在遍历结束后依旧需要在考虑进制的前提下将较长的链表没有遍历的节点依次放入新的链表中。
- 相关代码片段
/**
* 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位 数字。
* 请你将两个数相加，并以相同形式返回一个表示和的链表。
* 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//如果链表为null或只有1个0节点则返回另一个链表
if (l1 == null || (l1.val == 0 && l1.next == null)) {
return l2;
}
if (l2 == null || (l2.val == 0 && l2.next == null)) {
return l1;
}
//记录链表长度
int len1 = 0;
int len2 = 0;
//定义长链表和短链表
ListNode pl = l1;
ListNode ps = l2;
while (pl != null) {
pl = pl.next;
len1++;
}
while (ps != null) {
ps = ps.next;
len2++;
}
pl = l1;
ps = l2;
if (len1 < len2) {
pl = l2;
ps = l1;
}
ListNode cur = pl;
//将短的链表遍历完
while (ps != null) {
//对是否需要进位1进行判断
if (pl.val + ps.val >= 10) {
pl.val = (pl.val + ps.val) % 10;
if (pl.next == null) {
ListNode p = new ListNode(-1);
p.val = 1;
pl.next = p;
p.next = null;
} else {
pl.next.val++;
}
} else {
pl.val = (pl.val + ps.val);
}
pl = pl.next;
ps = ps.next;
}
//对较长链表的未遍历节点进行遍历
while (pl != null) {
if (pl.val >= 10) {
pl.val = pl.val % 10;
if (pl.next == null) {
ListNode p = new ListNode(-1);
p.val = 1;
pl.next = p;
p.next = null;
} else {
pl.next.val++;
}
}
pl = pl.next;
}
return cur;
}
合并k个升序链表
-
题目介绍
-
思路分析
- 这道题要求合并k个有序链表。我的切入点是先将链表数组中k个链表先进行两两合并,然后按照上述方式继续合并直到链表中所有链表都合并到一个链表为止
2. 这里提到的合并两个有序链表在我之前的这篇文章中单链表操作详解(反转、遍历)详细介绍过,大家如果有需要可以去看一下。
- 相关代码片段
/**
* 合并k个有序链表为1个有序链表
* @param lists
* @return
*/
public ListNode mergeKLists(ListNode[] lists) {
//如果链表集合为空则返回null
if(lists == null){
return null;
}
int length = lists.length;
//如果链表集合长度为0,则返回null
if(length == 0){
return null;
}
//如果链表集合中只有一个链表则返回该链表
if(length == 1){
return lists[0];
}
//在两两合并之前,先保证将链表的长度设置成偶数
if (length % 2 != 0) {
lists[0] = mergeTwoList(lists[0], lists[length - 1]);
length--;
}
//记录每次合并和的链表集合的长度
int k = 0;
//两两合并链表集合中的链表
while (length != 0) {
//两两合并
for (int i = 1; i < length; i += 2) {
lists[k++] = mergeTwoList(lists[i - 1], lists[i]);
}
//将合并后的链表集合的长度设置成偶数，方便下次两两合并的进行
if (k % 2 != 0 && k != 1) {
lists[0] = mergeTwoList(lists[0], lists[k - 1]);
k--;
}
//定义合并后新链表集合的真实长度
length = k;
k = 0;
}
//链表集合中的第一个集合保存了所有链表合并后的链表
return lists[0];
}
/**
* 将两个有序链表合并成一个有序链表
*/
public ListNode mergeTwoList(ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);
//虚拟头节点,起到连接的作用,最后会被JVM底层自动回收掉
ListNode tmp = newHead;
while (headA != null && headB != null) {
if (headA.val < headB.val) {
tmp.next = headA;
tmp = headA;
headA = headA.next;
} else {
tmp.next = headB;
tmp = headB;
headB = headB.next;
}
}
if (headA != null) {
tmp.next = headA;
}
if (headB != null) {
tmp.next = headB;
}
return newHead.next;
}
两两交换链表中的节点
-
题目介绍
-
思路分析
- 这道题要求两两交换链表中的节点。因此我们应该以两个节点作为一个单位考虑如何改变该单位的指向：首先每个单位的第二个节点由原来指向下一个节点改为指向前一个结点;每个单位的前一个结点由原来的指向后一个结点改为指向第二个单位的后一个节点。
- 经过遍历链表直到让每个单位的指向都改变，需要注意的是,当第二个单位没有后一个结点时,前一个单位的第一个结点的指向应该指向的是后一个单位的那唯一一个节点在最后一个单位中需要将第一个节点指向null
- 相关代码片段
**
* 两两交换链表中的节点
* @param head
* @return
*/
public ListNode swapPairs(ListNode head) {
//如果链表为空则返回null
if (head == null) {
return null;
}
//如果链表只有一个节点则返回该节点
if (head.next == null) {
return head;
}
//定义新的头节点即为原链表的第二个节点
ListNode newHead = head.next;
//定义一个单位中的前后节点
ListNode pre = head;
ListNode cur = head.next;
//对一个单位进行遍历改变相应的指向
while (pre != null && cur != null && cur.next != null) {
ListNode curNext = cur.next;
cur.next = pre;
//分开判断如果某个单位有1个节点或2个节点的情况
if (curNext.next != null) {
pre.next = curNext.next;
} else {
pre.next = curNext;
}
pre = curNext;
cur = curNext.next;
}
//操作最后一个单位的指向
if (cur != null) {
cur.next = pre;
}
pre.next = null;
return newHead;
}
总结
本文主要讲述了leetcode上关于链表习题的相关题解,这些题解仅代表我个人在做题时的一些想法，不能保证一定是最好的。大家合理阅读，自行取舍。希望大家能够有所收获！