一、返回单向有环链表中第一个入环的节点:
1.方法一:使用set。
思路:如果有环,那么遍历链表,某个节点被遍历到第二次的时候他就是第一个入环的节点。
使用set,遍历加入set,若某个节点之前被添加过了(第一次重复),将这个节点返回。
2.方法二:使用快慢指针。
1)慢指针slow(一次走一步),快指针fast(一次走两步);慢指针从head.next出发,快指针从head
next.next出发。开始遍历,在第一次两个指针相遇时,停止(表名此时链表内是有环的)。
2)然后让快指针回到head,变为一次走一步,慢指针维持在原地,保持一次走一步,他们一定会在第一个入环的节点相遇。返回这个节点。
//使用HashSet public ListNode EntryNodeOfLoop(ListNode head) { if(head == null || head.next == null || head.next.next==null) return null; HashSet<ListNode> set = new HashSet<>(); ListNode cur = head; while(cur != null){ if(set.add(cur)){ cur = cur.next; }else{ return cur; //代表有环,且cur就是入环节点 } }//while循环退出,表示无环,并且此时cur已经指向的是链表的结尾的next,也就是null,返回即可 return cur; }
//使用快慢指针 public static Node getLoopNode(Node head){ if(head == null || head.next == null || head.next.next == null) return null; Node slow = head.next; Node fast = head.next.next; while(slow != fast){ if(fast.next == null || fast.next.next == null){ return null; } fast = fast.next.next; slow = slow.next; } //上面while循环结束表示链表中有环,并且fast == slow fast = head; // 重置fast while(slow != fast){ slow = slow.next; fast = fast.next; } return slow; //最后相遇的位置就是第一个入环的节点 }
二、链表相交问题:
目标:找到相交的第一个节点,并返回,若不相交,返回null。
1.两个无环链表:
【思路】:1)若相交。相交之后的部分一定是共用的。因为单链表只有一个next指针。
方法一:使用set。思路与上述找有环链表的入环节点相同。
方法二:长链表先走比短链表多出来部分,然后再一起走,第一个相同的节点就是相交的位置。
2)若不相交。遍历两条链表至最后,若结尾不相同,则两条链表不相交。
【整理】:
1)首先判断链表是否相交。遍历两条链表至最后,若结尾不相同,则两条链表不相交。不相交,就返回null,若相交,进入下一步。
2)根据思路的方法二(代码如下)。(也可以使用思路的方法一)
public static Node noLoop(Node head1, Node head2){ if (head1 == null || head2 == null) return null; Node cur1 = head1; Node cur2 = head2; int n = 0; while (cur1.next != null){ n++; cur1 = cur1.next; } while (cur2.next != null){ n--; cur2 = cur2.next; } if (cur1 != cur2){ return null; // 说明没有相交 } cur1 = n > 0 ? head1 : head2; //将长链表的头给cur1 cur2 = cur1 == head1 ? head2 : head1; // 将短链表的 头,给cur2 //n为两个链表长度的差值 n = Math.abs(n); while (n != 0){//cur1先走 n--; cur1 = cur1.next; } while (cur1 != cur2){//cur1和cur2一起走,直到相遇结束 cur1 = cur1.next; cur2 = cur2.next; } return cur1; }
2.一个无环链表和一个有环链表是不可能相交的。
3.两个有环链表:两个有环链表相交,则他们一定共用这个环。
这种情况下:问题转化为求无环链表的相交节点。
情况三:入环节点是两个,但各自成环,即不相交,返回null。
思路:先去判断属于哪种情况然后在处理相交。
//两个有环链表,返回第一个相交节点,没有返回null。loop为链表的入环节点。 public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){ Node cur1 = null; Node cur2 = null; //第一种情况 if (loop1 == loop2){ cur1 = head1; cur2 = head2; int n = 0; while (cur1 != loop1){ n++; cur1 = cur1.next; } while (cur2 != loop2){ n--; cur2 = cur2.next; } cur1 = n > 0 ? head1 : head2; //将长链表的头给cur1 cur2 = cur1 == head1 ? head2 : head1; // 将短链表的 头,给cur2 //n为两个链表长度的差值 n = Math.abs(n); while (n != 0){//cur1先走 n--; cur1 = cur1.next; } while (cur1 != cur2){//cur1和cur2一起走,直到相遇结束 cur1 = cur1.next; cur2 = cur2.next; } return cur1; }else {//相交的节点不相等 cur1 = loop1.next; while (cur1 != loop1){//从入环节点开始,若转回到自己,则说明不相交,返回null if (cur1 == loop2){ return loop1;//loop1、loop2都是相交的节点 } cur1 = cur1.next; } return null; } }
主方法:
public static Node getIntersectNode(Node head1, Node head2){ if (head1 == null || head2 == null){ return null; } //获得两个链表的入环节点 Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); if (loop1 == null && loop2 == null){ //如果都为空,表明他们都为非带环链表,使用方法noLoop()处理; return noLoop(head1,head2); } //如果都不为空,表明他们都为带环链表,使用方法bothLoop()处理; if (loop1 != null && loop2 != null){ return bothLoop(head1,loop1,head2,loop2); } return null; //剩下情况直接返回null }