24. 两两交换链表中的节点
题目链接:24. 两两交换链表中的节点
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰两两交换链表中的节点
日期:2024-08-31
做前思路:用上虚拟头指针,从头开始,先指向2再到1,再到3,但要注意保留原本的结点。
Java代码如下:
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode node1;
ListNode node2;
ListNode node3;
ListNode cur = dummyHead;
while(cur.next != null && cur.next.next != null){
node1 = cur.next;
node2 = cur.next.next;
node3 = cur.next.next.next;
cur.next = node2;
cur.next.next = node1;
cur.next.next.next = node3;
cur = cur.next.next;
}
return dummyHead.next;
}
}
总结:做此题得有图,我为了方便就将当前结点后的3个结点全部保存了一遍,当然也可以省略一些。
19.删除链表的倒数第N个节点
题目链接:19.删除链表的倒数第N个节点
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰删除链表的倒数第N个节点
日期:2024-08-31
做前思路:第一反应要是删除的是第n个结点,而不是倒数第n个就好了,遍历一遍链表得到它长度,将其还算为删除第m个结点;当然在,学习后会想到快慢双指针来,实际上我认为这是一个数学小技巧,快指针先走n步后,快慢指针一起走,快指针走到尾,此时慢指针就在要删的结点那个位置了,当然,为了后面删除操作更方便,我们需要将慢指针移前一位,所以快指针走n+1不就行了。
Java代码如下:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
while(n-- > 0){
fast = fast.next;
}
fast = fast.next;//快指针走n+1
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
总结:这也算是一道双指针来优化算法的案例,双指针作用主要体现在了简单的数学加减上,能够定位到倒数n个结点的位置才是关键。
面试题 02.07. 链表相交
题目链接:面试题 02.07. 链表相交
文档讲解︰代码随想录(programmercarl.com)
日期:2024-08-31
做前思路:想象两个相同长度的链表,要找它们相交点,只需要依次一个一个对比每一个指针是不是有相同就行,指针一旦相同,后面的内容也一定会相同(链表的基本属性了),而如果两个长度不一样的呢,如果还从头依次开始比,那么永远找不到相同的指针,因为最基本的它们链表长度都不一样了,怎么还能相交呢(这里链表只能1对1,1对多那是树了),所以我们只有想办法先将两根链表尾部对齐后,才能再按照两个相同长度的链表一样的操作,找到相交位置。
Java代码如下:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != null){
curA = curA.next;
lenA++;
}
while(curB != null){
curB = curB.next;
lenB++;
}
curA = headA;
curB = headB;
if(lenB > lenA){
curA = headB;
curB = headA;
int temp = lenA;
lenA = lenB;
lenB = temp;
}
int gap = lenA - lenB;
while(gap-- > 0){
curA = curA.next;
}
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
总结:做题时出了个错,想了挺久代码是这样的:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != null){
curA = curA.next;
lenA++;
}
while(curB != null){
curB = curB.next;
lenB++;
}
//curA = headA; 这两个没有
//curB = headB;
if(lenB > lenA){
curA = headB;
curB = headA;
int temp = lenA;
lenA = lenB;
lenB = temp;
}
int gap = lenA - lenB;
while(gap-- > 0){
curA = curA.next;
}
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
当时想着我不是已经curA = headB; curB = headA;了吗,却没有考虑到当lanA > lanB情况下cuaA, cuaB仍是null,通过debug才搞明白。
**142.环形链表II **
题目链接:142.环形链表II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰环形链表II
日期:2024-08-31
做前思路:一道颇有难度,用上快慢指针和数学思维的题,首先,考虑快慢指针是来干什么,找是不是有环,如果快的走两步能追上慢的走一步的,那一定是有环的,然后是怎么找入口,这点建议直接看文档,这里权当是记住了该怎么找,作为结论:两个指针一个是在头,一个是在相遇点,一起前进一步,相遇点便是入口。
Java代码如下:
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
ListNode index1 = fast;
ListNode index2 = head;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
总结:代码简洁的后果就是逻辑的要求增多,确定有没有环比较好理解,找入口只能先记住了,推导再议。
标签:ListNode,随想录,fast,next,链表,curB,curA,节点 From: https://www.cnblogs.com/wowoioo/p/18390559