代码随想录第四天 | 链表part02
[*]两两交换链表中的节点
用虚拟头结点，这样会方便很多。
本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.两两交换链表中的节点.html
题目感想：
1.面对链表的题目为了方便处理，定义一个虚拟头节点，大概的思路就是，先让指针指向当前节点的NEXT节点,先保存NEXT节点的原始NEXT节点，然后使得NEXT节点的NEXT为它的前置节点，这样1、2节点的位置就替换过来了，然后cur指针再指向刚刚保存的那个节点，开始下一步操作；
public ListNode swapPairs(ListNode head) {
ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
ListNode cur = dumyhead;
ListNode temp; // 临时节点，保存两个节点后面的节点
ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
while (cur.next != null && cur.next.next != null) {
temp = cur.next.next.next;
firstnode = cur.next;
secondnode = cur.next.next;
cur.next = secondnode; // 步骤一
secondnode.next = firstnode; // 步骤二
firstnode.next = temp; // 步骤三
cur = firstnode; // cur移动，准备下一轮交换
}
return dumyhead.next;
}
// 将步骤 2,3 交换顺序，这样不用定义 temp 节点
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
ListNode node1 = cur.next;// 第 1 个节点
ListNode node2 = cur.next.next;// 第 2 个节点
cur.next = node2; // 步骤 1
node1.next = node2.next;// 步骤 3
node2.next = node1;// 步骤 2
cur = cur.next.next;
}
return dummy.next;
}2.还有一种方法是使用递归，先通过递归抵达链表末尾，递归回去的时候，就进行交换
public ListNode swapPairs(ListNode head) {
// base case 退出提交
if(head == null || head.next == null) return head;
// 获取当前节点的下一个节点
ListNode next = head.next;
// 进行递归
ListNode newNode = swapPairs(next.next);
// 这里进行交换
next.next = head;
head.next = newNode;
return next;
}19.删除链表的倒数第N个节点
双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0019.删除链表的倒数第N个节点.html
题目感想：
1.这里也定义虚拟头节点，然后通过快慢指针，因为要删除倒数的第N个节点，也就是距离尾部的距离为N的节点，所以我们先定义两个指针，快指针要先于慢指针走N个节点，然后两个节点再一起走，直到快指针抵达链表末尾；
2.需要注意定义了虚拟头节点的影响，以及快指针和慢指针之间的距离，慢指针停留下来要在想要删除节点的前面，这样才能便于删除操作；
public ListNode removeNthFromEnd(ListNode head, int n) {
//新建一个虚拟头节点指向head
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//快慢指针指向虚拟头节点
ListNode fastIndex = dummyNode;
ListNode slowIndex = dummyNode;
// 只要快慢指针相差 n 个结点即可
for (int i = 0; i <= n; i++) {
fastIndex = fastIndex.next;
}
while (fastIndex != null) {
fastIndex = fastIndex.next;
slowIndex = slowIndex.next;
}
// 此时 slowIndex 的位置就是待删除元素的前一个位置。
// 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
// 检查 slowIndex.next 是否为 null，以避免空指针异常
if (slowIndex.next != null) {
slowIndex.next = slowIndex.next.next;
}
return dummyNode.next;
}3.第二种方法就是定义两个指针分别开始遍历两个链表，遍历完本链表就去遍历另外一条链表，如果遍历期间有相同的指针就是入口了。
这个原因是假设两个链表相交，那么他们的相同部分是c，不同部分分别是a,b,那么按照上述遍历，将会走同样长的路程就能得到入口点了；
(版本一)先行移动长链表实现同步移动
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
//1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
//2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}142.环形链表II
算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.环形链表II.html
题目感想：
1.首先我们要确定是否有环，可以定义两个快慢指针，快指针一下走两个，慢指针一下走一个，如果有环的话他们一定会相交，没有环的就会遍历到链表末尾；
2.有环就需要找到环的入口，这个推到过程可以去看上面的链接里面，详细介绍了为什么会在慢指针走在环中的第一圈相遇，以及为什么定义两个指针，一个从相遇节点出发，一个从起始节点出发，每次走一格，最终相遇的地方是环的入口；
(版本二) 合并链表实现同步移动
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]