25、复杂链表的复制 (map+分段)
import java.util.HashMap; public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead==null){ return null; } HashMap<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>(); RandomListNode p=pHead; //遍历将数据放到map中 while(p!=null){ map.put(p,new RandomListNode(p.label)); p=p.next; } //复制random和next值 p=pHead; while(p!=null){ map.get(p).next=map.get(p.next); map.get(p).random=map.get(p.random); p=p.next; } return map.get(pHead); } }
/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead==null){ return null; } RandomListNode p=pHead; ///第一步，首先复制链表和val while(p!=null){ RandomListNode cloneNode=new RandomListNode(p.label); RandomListNode nextNode=p.next; p.next=cloneNode; cloneNode.next=nextNode; p=nextNode; } p=pHead; ///第二步，将复制链表中random和next while(p!=null){ p.next.random=p.random==null?null:p.random.next; p=p.next.next; } ///第三步，拆分链表 RandomListNode pcloneNode=pHead.next; p=pHead; while(p!=null){ RandomListNode cloneNode=p.next; p.next=cloneNode.next; cloneNode.next=cloneNode.next==null?null:cloneNode.next.next; p=p.next; } return pcloneNode; } }
36、两链表的第一个公共节点
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null){ return null; } int p1length=0; ListNode p1=pHead1; while(p1!=null){ p1length++; p1=p1.next; } int p2length=0; ListNode p2=pHead2; while(p2!=null){ p2length++; p2=p2.next; } p1=pHead1; p2=pHead2; int count=Math.abs(p2length-p1length); if(p2length>p1length){ for(int i=0;i<count;i++){ p2=p2.next; } }else{ for(int i=0;i<count;i++){ p1=p1.next; } } while(p1!=null&&p2!=null){ if(p1==p2){ return p1; } p1=p1.next; p2=p2.next; } return null; } }
两链表的头指针同时出发，当第二次经过第一个公共节点时，会完美相遇
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1=pHead1; ListNode p2=pHead2; while(p1!=p2){ p1=p1!=null?p1.next:pHead2; p2=p2!=null?p2.next:pHead1; } return p1; } }
55、链表中环的入口节点
根据定理，fast，slow指针(快指针走2步，慢指针走1步)，如果有环一定会相遇；从相遇点开始 和从 链表的PHead开始走，分别走一步，最终一定会相遇。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode fast=pHead; ListNode slow=pHead; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ break; } } if(fast==null||fast.next==null){ return null; } fast=pHead; while(fast!=slow){ fast=fast.next; slow=slow.next; } return fast; } }
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ import java.util.HashSet; public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { HashSet<ListNode> set=new HashSet<ListNode>(); while(pHead!=null){ if(set.contains(pHead)){ return pHead; }else{ set.add(pHead); } pHead=pHead.next; } return null; } }