环形链表I
解法一
哈希集合
遍历链表并判断哈希集合里面是否包含当前节点
如果包含则存在环
public class Solution { public boolean hasCycle(ListNode head) { HashSet<ListNode> set = new HashSet<>(); while(head != null){ if(set.contains(head)) return true; else set.add(head); head = head.next; } return false; } }
解法二
双指针
一个quick指针一个slow指针
quick每次走两步
slow每次走一步
假如没有环
那么quick就会为空，直接返回false
如果有环
那么quick回比slow先进入环，slow后进入环
他们总会在环里相遇所有quick == slow
public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; ListNode quick = head.next; ListNode slow = head; while(quick != slow){ // 不相等就一直循环 if(quick == null || quick.next == null) return false; // 如果为空直接退出 quick = quick.next.next; slow = slow.next; } return true; } }
环形链表II
解法一
哈希集合
如果在该哈希集合中存在就返回当前节点
public class Solution { public ListNode detectCycle(ListNode head) { HashSet<ListNode> set = new HashSet<>(); while(head != null){ if(set.contains(head)) return head; else set.add(head); head = head.next; } return null; } }
解法二
双指针
像环形链表1一样可以找到相遇节点
然后slow指向头节点，然后quick与slow每次向后移动一步直到相遇
所以下次相遇时候就是第一个节点
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null)return head; ListNode quick = head; ListNode slow = head; while(true){ if(quick == null || quick.next == null) return null; quick = quick.next.next; slow = slow.next; if(quick == slow) break; } slow = head; while(quick != slow){ slow = slow.next; quick = quick.next; } return quick; } }
注意！！！
如果相遇那个方法是第一种的话，即quick = head.next
那么quick需要在相遇之后再向移动一个位置，推到如上
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null)return head; ListNode quick = head.next; ListNode slow = head; while(quick != slow){ if(quick == null || quick.next == null) return null; quick = quick.next.next; slow = slow.next; } slow = head; quick = quick.next; while(quick != slow){ slow = slow.next; quick = quick.next; } return quick; } }
排序链表
解法一
使用优先队列
先循环一遍把当前节点放进去，再重构有序链表
class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; PriorityQueue<ListNode> p = new PriorityQueue<>((l1,l2)->l1.val-l2.val); ListNode t = head; while(t != null){ // 遍历进优先队列 p.add(t); t = t.next; } ListNode res = new ListNode(); t = res; while(!p.isEmpty()){ // 重构 ListNode node = p.poll(); t.next = node; t = t.next; } t.next = null; // 避免出现环 return res.next; } }
解法二
归并排序
从顶到底
class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode quick = head.next; ListNode slow = head; while(quick != null && quick.next != null){ quick = quick.next.next; slow = slow.next; } ListNode mid = slow.next; slow.next = null; // 将一个链表断开为两个链表 ListNode left = sortList(head); ListNode right = sortList(mid); // 相当于两个有序链表的合并 ListNode res = new ListNode(); ListNode t = res; while(left != null && right != null){ if(left.val < right.val){ t.next = left; left = left.next; }else{ t.next = right; right = right.next; } t =t.next; } if(left != null) t.next = left; if(right != null) t.next = right; return res.next; } }
