24. 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
一道模拟题，我的第一版解法
// 双指针不断移动，交换数据
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode left = head;
ListNode right = head.next;
ListNode preRight = null;
head = right;
while (left != null && right != null) {
ListNode tmp = right.next;
left.next = tmp;
right.next = left;
if (preRight != null) {
preRight.next = right;
}
if (tmp == null) {
break;
} else {
preRight = left;
left = tmp;
right = tmp.next;
}
}
return head;
}
}
卡哥更简洁的解法
class Solution {
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;
}
}
题后感：
1.和卡哥的解法逻辑上是一致的，但我的代码不够简洁
2.链表题一定要画图，否则很容易绕晕
3.学会使用虚拟节点方法，在链表题中卡哥基本都用到了
19.删除链表的倒数第N个节点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
该题用非常高频使用的快慢指针的解法，比较简单
// 第一版解法 - 没有使用虚拟节点，需要处理只有一个元素的边界情况
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n <= 0) {
return head;
}
if (head.next == null && n == 1) {
head = null;
return head;
}
ListNode slow = head;
ListNode fast = head;
// 快走n步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 开始移动判断,快指针不是最后一个元素
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
// 删除元素
slow.next = slow.next.next;
return head;
}
}
// 第二版解法 - 使用虚拟节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fakeNode = new ListNode(0);
fakeNode.next = head;
ListNode slow = fakeNode;
ListNode fast = fakeNode;
// 快走n步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 开始移动判断,快指针不是最后一个元素
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
// 删除元素
slow.next = slow.next.next;
// !!!!注意最后返回值
return fakeNode.next;
}
}
面试题 02.07. 链表相交
同 https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
int lenB = 0;
ListNode curA = headA;
ListNode curB = headB;
while (curA != null) {
lenA++;
curA = curA.next;
}
while (curB!= null) {
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
int step = 0;
if (lenA - lenB >= 0) {
step = lenA - lenB;
} else {
step = lenB - lenA;
curA = headB;
curB = headA;
}
while(step > 0) {
curA = curA.next;
step--;
}
while (curA != null && curB != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
这道题刚开始没想到先计算长度差、长链表快走n步的方法，也想了很久，知道解法就好做。坑也少。代码逻辑基本一致。
142.环形链表II
https://leetcode.cn/problems/linked-list-cycle-ii/description/
判断是否有环，如果有环，返回入环的第一个节点
(若干年前毕业找工作的时候《剑指offer》里看到过？)
// 看完解法之后的版本
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
// 判断是否有环
ListNode slow = head;
ListNode fast = head;
ListNode seeNode = null;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
seeNode = slow;
break;
}
}
// 找环入口
if (seeNode == null) {
return null;
}
ListNode tmpNode = head;
while (tmpNode != null) {
if (tmpNode == seeNode) {
return tmpNode;
}
tmpNode = tmpNode.next;
seeNode = seeNode.next;
}
return null;
}
}
// 卡哥简洁版
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {// 有环
ListNode index1 = fast;
ListNode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
题后感
1.快慢指针检测有环这个解法是之前就知道的，但是求入口环不知道，没想到还要列公式，不知道实际面试的时候难道还得自己推导一遍吗？
2.自己看完题的解法之后第一个版本问题在判断是否有环的条件上
初始化时，对slow及fast的赋值是在外面还是在里面，如果在while之外初始化的时候就赋值，那需要单独判断next的有效性，while条件里也要判断，这个时候就有重复了，不简洁
