链表节点定义
public class ListNode { // 结点的值 int val; // 下一个结点 ListNode next; // 节点的构造函数(无参) public ListNode() { } // 节点的构造函数(有一个参数) public ListNode(int val) { this.val = val; } // 节点的构造函数(有两个参数) public ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
*移除链表节点
题目链接：https://leetcode.cn/problems/reverse-linked-list/
【思路】
有时候增加一个虚拟节点，可以让后面的操作都一致
public static ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } // 增加一个虚拟节点 ListNode virtualNode = new ListNode(); virtualNode.next = head; ListNode cur = virtualNode; ListNode next = cur.next; while (next != null) { if (next.val == val) { cur.next = next.next; } else { cur = next; } next = cur.next; } return virtualNode.next; }
*反转链表
双指针法
- 时间复杂度: O(n)
- 空间复杂度: O(1)
public static ListNode reverseList(ListNode head) { ListNode cur = head; ListNode pre = null; ListNode temp = null; while (cur != null) { temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }
递归法
- 时间复杂度: O(n)
- 空间复杂度: O(n)
这里的逻辑和双指针法的逻辑是一样的，只是实现方式是递归，那为什么空间复杂度更高呢？
答：因为递归本质上是一种函数调用，在每一次递归调用时，都会在函数栈中分配一段内存空间来保存函数的局部变量、返回地址以及参数等信息。因此，递归实现相对于循环实现的空间复杂度更高，会占用更多的内存空间。尤其是在递归深度较大的情况下，可能会导致栈溢出等问题。而使用循环实现通常不需要使用额外的栈空间，因此循环实现的空间复杂度比递归实现要低
public static ListNode reverseList1(ListNode head) { return reverse(null, head); } public static ListNode reverse(ListNode pre, ListNode cur) { if (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = reverse(cur, temp); } return pre; }
*两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/
- 时间复杂度：O(n)
- 空间复杂度：O(1)
public static ListNode swapPairs(ListNode head) { // 如果链表中没有元素 或者 只有一个元素，直接返回就行 if (head == null || head.next == null) { return head; } // 增加一个虚拟头节点 ListNode virtualNode = new ListNode(); virtualNode.next = head; ListNode last = virtualNode; ListNode cur = head; ListNode next = cur.next; ListNode temp = null; while (next != null) { // 交换 temp = next.next; cur.next = next.next; next.next = cur; last.next = next; // 指针移动到新的位置 last = cur; cur = temp; if (cur != null) { next = cur.next; } else { break; } } return virtualNode.next; }
*删除链表的倒数第N个节点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/submissions/
快慢指针法
/** * 让快指针比慢指针先移动 n 步 * * @param head * @param n * @return */ public static ListNode removeNthFromEnd(ListNode head, int n) { ListNode virtual = new ListNode(); virtual.next = head; // 让快指针先移动到n个节点 ListNode fast = virtual; for (int i = 0; i < n; i++) { if (fast.next != null) { fast = fast.next; } } // slow和fast一起移动，等fast到达最后一个节点的时候，slow也就到达了要删除的节点前面的节点 ListNode slow = virtual; while (fast.next != null) { slow = slow.next; fast = fast.next; } // 执行删除操作 slow.next = slow.next.next; return virtual.next; }
- 时间复杂度: O(n)
- 空间复杂度: O(1)
*链表相交
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
注意点
并不是判断val相等，而是hashcode相等
暴力求解
直接两重循环，循环两个链表
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
进阶解法
利用题目中的信息，已经是链表的尾部才有可能相交，可以先让一条链表前进 两条链表长度差值 的位置，最后再两条链表一起前进
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode cur1 = headA; ListNode cur2 = headB; int sizeA = 0; int sizeB = 0; // 统计链表A的长度 while (cur1 != null) { sizeA += 1; cur1 = cur1.next; } // 统计链表B的长度 while (cur2 != null) { sizeB += 1; cur2 = cur2.next; } // 回到初始位置 cur1 = headA; cur2 = headB; // 先让元素较多的链表的指针移动一段距离 if (sizeA > sizeB) { // 链表A的元素较多，先走一段距离 for (int i = 0; i < (sizeA - sizeB); i++) { cur1 = cur1.next; } } else if (sizeA < sizeB) { for (int i = 0; i < (sizeB - sizeA); i++) { cur2 = cur2.next; } } // 两个链表同时走动 while (cur1 != null && cur2 != null) { // 注意，需要的是hash值 if (cur1.hashCode() == cur2.hashCode()) { return cur1; } cur1 = cur1.next; cur2 = cur2.next; } return null; }
- 时间复杂度：O(n + m)
- 空间复杂度：O(1)
*环形链表
https://leetcode.cn/problems/linked-list-cycle-ii/
public static ListNode detectCycle1(ListNode head) { if (head == null) { return null; } ListNode slow = head; ListNode fast = head; ListNode node2 = null; // 先找到相交点 while (slow != null && fast.next != null) { // slow移动一步 slow = slow.next; // fast移动两步 fast = fast.next.next; if (slow.hashCode() == fast.hashCode()) { // slow 和 fast相交 node2 = slow; // 让node1从起点出发，node2从相交点出发，当node1和node2相交的时候，相交时的节点即环的入口 ListNode node1 = head; while (true) { if (node1.hashCode() == node2.hashCode()) { return node1; } else { node1 = node1.next; node2 = node2.next; } } } } return null; }
- 时间复杂度: O(n)。因为快慢指针相遇前，指针走的次数小于链表长度；快慢指针相遇后，两个node指针走的次数也小于链表长度，因此走的总次数小于 2n
- 空间复杂度: O(1)
