【算法】链表题型总结

链表题型可分为快慢指针和虚拟头节点两种解题技巧。

快慢指针

使用两个指针（快指针和慢指针），以不同的速度遍历链表，解决与链表位置、环检测相关的问题。

反转链表

快慢指针，慢指针一次走一步，快指针一次走两步，直到快指针为null，返回慢指针节点

public ListNode middleNode(ListNode head){ ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } 判断回文链表

找到链表中间节点 + 反转后段链表，然后比较前后两段链表是否相等

环形链表

判断是否有环：快慢指针，慢指针一次走一步，快指针一次走两步，如果相遇说明有环

public boolean hasCycle(ListNode head) { ListNode last = head; ListNode fast = head; while (fast != null && fast.next != null){ if (fast == last){ return true; } fast = fast.next.next; last = last.next; } return false; }

找到环的首个节点：first指针指向头节点，second指针指向当前快指针，两个指针同时遍历到相遇

if (last == fast){ ListNode first = head; ListNode second = fast; while (first != second){ first = first.next; second = second.next; } return first; } 删除链表倒数第N个节点

快慢指针，快指针先走n个节点，然后快慢指针同时移动，当快指针为null，删除慢指针。

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dumy = new ListNode(0); dumy.next = head; ListNode last = dumy; ListNode fast = head; for (int i = 0; i < n; i ++){ fast = fast.next; } while (fast != null){ fast = fast.next; last = last.next; } last.next = last.next.next; return dumy.next; } 虚拟头节点

在链表头部添加一个虚拟节点（dummy node），简化边界条件处理，尤其是涉及头节点操作的问题。

合并两个升序链表

创造虚拟头节点，然后比较两个链表，依次向后添加

public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dump = new ListNode(0); ListNode cur = dump; while (list1 != null && list2 != null){ if (list1.val < list2.val){ cur.next = list1; list1 = list1.next; }else{ cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null){ cur.next = list1; } if (list2 != null){ cur.next = list2; } return dump.next; } 链表相加

创造虚拟头节点，依次相加两链表节点，sum = x + y + carry，carry = sum/10，sum = sum % 10

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dump = new ListNode(0); ListNode cur = dump; int carry = 0; while (l1 != null || l2 != null){ int x = 0, y = 0; if (l1 != null){ x = l1.val; } if (l2 != null){ y = l2.val; } int sum = x + y + carry; carry = sum / 10; sum = sum % 10; cur.next = new ListNode(sum); cur = cur.next; if (l1 != null){ l1 = l1.next; } if (l2 != null){ l2 = l2.next; } } if (carry == 1){ cur.next = new ListNode(carry); } return dump.next; } 两两交换链表中的节点

创造虚拟头节点，创建one节点指向虚拟头节点，two节点 = one.next，three节点 = one.next.next，temp提前存one.next.next.next，然后one.next = three，three.next = two，two.next = temp

public ListNode swapPairs(ListNode head) { ListNode dumy = new ListNode(0); dumy.next = head; ListNode one = dumy; ListNode two; ListNode three; while (one.next != null && one.next.next != null){ ListNode temp = one.next.next.next; two = one.next; three = one.next.next; one.next = three; three.next = two; two.next = temp; one = two; } return dumy.next; } 排序链表

归并排序，把当前链表一分为二（找到链表中间节点），再对左右子链表递归排序（合并两个升序链表）

public ListNode sortList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode mid = findMiddle(head); ListNode rightHead = mid.next; mid.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); return mergeTwoLists(left, right); } private ListNode findMiddle(ListNode head){ ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null){ slow = slow.next; fast = fast.next; } return slow; } private ListNode mergeTwoLists(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(0); ListNode curr = dummy; while (l1 != null && l2 != null){ if (l1.val < l2.val){ curr.next = l1; l1 = l1.next; }else { curr.next = l2; l2 = l2.next; } curr = curr.next; } if (l1 != null){ curr.next = l1; } if (l2 != null){ curr.next = l2; } return dummy.next; } 其他  相交链表

两个指针，先遍历出两个链表的长度，然后长链表和短链表同一长度（长链表指针先遍历长度差的节点），最后比较两段链表是否相等

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