链表题型可分为快慢指针和虚拟头节点两种解题技巧。
快慢指针
使用两个指针(快指针和慢指针),以不同的速度遍历链表,解决与链表位置、环检测相关的问题。
反转链表
-
快慢指针,慢指针一次走一步,快指针一次走两步,直到快指针为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;}
其他
相交链表
-
两个指针,先遍历出两个链表的长度,然后长链表和短链表同一长度(长链表指针先遍历长度差的节点),最后比较两段链表是否相等