【两个月算法速成】day04

                                           本文以收录专题刷题记录

目录

24. 两两交换链表中的节点

题目链接

思路

代码

19. 删除链表的倒数第 N 个结点

题目链接

思路-双指针

代码

面试题 02.07. 链表相交

题目链接

思路

代码

---

24. 两两交换链表中的节点

题目链接

力扣

思路

建议使用虚拟节点，这样每次对头结点操作就不需要单独处理了

接下来就是简单的模拟过程

一定要画图 不然指针指来指去容易乱

代码

class Solution {public ListNode swapPairs(ListNode head) {ListNode node = new ListNode(0);node.next = head;ListNode cur = node;while (cur.next != null && cur.next.next != null){ListNode temp = cur.next.next;cur.next = head.next;head.next = temp.next;temp.next = head;cur = head;head = cur.next;}return node.next;}
}

19. 删除链表的倒数第 N 个结点

题目链接

力扣

思路-双指针

在这里我们尝试进阶写法,只使用一次遍历得到结果。

首先使用虚拟头结点，这样方便处理删除实际头结点的逻辑。

定义fast指针和slow指针，初始值为虚拟头结点，fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）。

fast和slow同时移动，直到fast指向末尾，删除slow指向的下一个节点

代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyhead = new ListNode(-1);dummyhead.next = head;ListNode fast = dummyhead;ListNode slow = dummyhead;while (n -- > 0){fast = fast.next;}while (fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyhead.next;}
}

面试题 02.07. 链表相交

题目链接

力扣

思路

注意交点不是数值相等，而是指针相等。

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0,lenB = 0;while (curA != null){lenA ++;curA = curA.next;}while (curB != null){lenB ++;curB = curB.next;}if (lenA > lenB){lenA = lenA - lenB;lenB = 0;}else {lenB = lenB - lenA;lenA = 0;}curA = headA;curB = headB;while (lenA-- > 0){curA = curA.next;}while (lenB -- > 0){curB = curB.next;}while (curA != null){if (curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}