代码随想录day04
24. 两两交换链表中的节点
● 力扣题目链接
● 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
● 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
● 使用迭代的方法，分析交换逻辑即可
○ 注意，可能链表节点个数奇数或偶数，分开讨论
○ 时间复杂度O(n) 空间复杂度O(1)
● 递归方法，时间复杂度O(n) 空间复杂度O(n)
○ 注意保存临时节点
代码
// 迭代
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head; // 空或单个节点直接返回ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;ListNode temp;while (cur != null && cur.next != null) { // 节点个数可能为奇数或偶数temp = cur.next;pre.next = temp;cur.next = temp.next;temp.next = cur;pre = cur;cur = pre.next;}return dummy.next;}
}
// 递归
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode reHead = swapPairs(head.next.next);ListNode temp = head.next;temp.next = head;head.next = reHead;return temp;}
}
19.删除链表的倒数第N个节点
● 力扣题目链接
● 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路
● 双指针，快指针先走n步，然后快慢指针一起走，快指针到末尾，慢指针到要删除元素的前一个元素，删除即可
● 使用栈，空间复杂度为O(n) 先依次入栈，然后弹出n个元素，这时栈顶的正好是要删除节点的前一个节点，删除即可（注意虚拟头节点也入栈，不然删除头结点时会空指针）
代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1, head);ListNode f = dummy, s = dummy;while (n-- > 0) {f = f.next;}while (f.next != null) {f = f.next;s = s.next;}s.next = s.next.next;return dummy.next;}
}
// 使用栈
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {Deque<ListNode> stack = new ArrayDeque();ListNode dummy = new ListNode(-1, head);ListNode cur = dummy;while (cur != null) {stack.addFirst(cur);cur = cur.next;}for (int i = 0; i < n; i++) {stack.removeFirst();}ListNode pre = stack.peek();pre.next = pre.next.next;return dummy.next;}
}
面试题 02.07. 链表相交
● 力扣题目链接
● 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
● 先求两个链表的长度，然后通过gap让两个链表尾部对齐，之后同时走，看会不会相遇，就是headA = headB
● 更快的方法，A和B同时遍历，走到空就从另一个链表头部继续遍历，如果相交就到相交节点，如果不相交就到空，时间复杂度O(m+n) 空间复杂度O(1)
代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = getLen(headA);int lenB = getLen(headB);if (lenB > lenA) { // B长就交换长度和头结点int tempLen = lenA;lenA = lenB;lenB = tempLen;ListNode tempNode = headA;headA = headB;headB = tempNode;}int gap = lenA - lenB;while (gap-- > 0) { // 尾部对齐headA = headA.next;}while (headA != null) {if (headA == headB) return headA;headA = headA.next;headB = headB.next;}return null;}// 求链表长度private int getLen(ListNode head) {int len = 0;while (head != null) {len++;head = head.next;}return len;}
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tA = headA;ListNode tB = headB;while (tA != tB) {tA = tA != null ? tA.next : headB;tB = tB != null ? tB.next : headA;}return tA;}
}
142.环形链表II
● 力扣题目链接
● 题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
● 为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
思路
● 快慢指针处理即可
代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode f = head, s = head;while (f != null && f.next != null) { // 快指针一次走两步，注意判空f = f.next.next;s = s.next;if (f == s) { // 相遇，有环f = head; // 快指针回到头结点while (f != s) {f = f.next;s = s.next; // 一起向前走}return f; // 找到入环节点}}return null; // 没有环，返回null}
}