双指针技巧秒杀七道链表题目

文档阅读

文档阅读

题目

141. 环形链表

https://leetcode.cn/problems/linked-list-cycle/

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

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}}return null;}
}

160. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p = headA, q = headB;while(p != q){p = p != null ? p.next : headB;q = q != null ? q.next : headA;}return p;}
}

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dumpy = new ListNode();dumpy.next = head;ListNode slow = dumpy;for(int i = 0; i < n; i++){if(head == null) return null;head = head.next;}while(head != null){slow = slow.next;head = head.next;}slow.next = slow.next.next;//deletereturn dumpy.next;}
}

21. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dumpy = new ListNode();ListNode help = dumpy;while(list1 != null && list2 != null){if(list1.val > list2.val){help.next = list2;list2 = list2.next;}else{help.next = list1;list1 = list1.next;}help = help.next;}if(list1 != null) help.next = list1;if(list2 != null) help.next = list2;return dumpy.next;}   
}

23. 合并 K 个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

class Solution {public ListNode mergeKLists(ListNode[] lists) {return mergerSort(lists, 0, lists.length - 1);}public ListNode mergerSort(ListNode[] lists, int left, int right){if(left == right) return lists[left];if(left > right) return null;int mid = (left + right) >> 1;ListNode leftNode = mergerSort(lists, left, mid);ListNode rightNode = mergerSort(lists, mid + 1, right);return mergerTowList(leftNode, rightNode);}public ListNode mergerTowList(ListNode left, ListNode right) {if (left == null) return right;if (right == null) return left;ListNode help = new ListNode(Integer.MIN_VALUE);ListNode cur = help;while (left != null && right != null) {if (left.val <= right.val) {cur.next = left;left = left.next;} else {cur.next = right;right = right.next;}cur = cur.next;}cur.next = left == null ? right : left;return help.next;}
}

86. 分隔链表

https://leetcode.cn/problems/partition-list/

class Solution {public ListNode partition(ListNode head, int x) {ListNode leftHead = new ListNode(-888);ListNode left = leftHead;ListNode rightHead = new ListNode(-888);ListNode right = rightHead;while(head != null){if(head.val < x){left.next = head;left = left.next;}else{right.next = head;right = right.next;}ListNode temp = head.next;head.next = null;head = temp;}left.next = rightHead.next;return leftHead.next;}
}

876. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}