【数据结构_6下篇】有关链表的oj题

思路：

1.分别求出这两个链表的长度

2.创建两个引用，指向两个链表的头节点；找到长度长的链表，让她的引用先走差值步数

3.让这两个引用，同时往后走，每个循环各自走一步

然后再判定两个引用是否指向同一个节点，如果发现相同，那么就说明该节点就是链表的交点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public int size (ListNode head){int size =0;for(ListNode cur = head;cur != null;cur = cur.next){size++;}return size;}public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//1.首先求出两个链表各自的长度int sizeA=size(headA);int sizeB =size(headB);//2.判断谁更长 让更长的链表先走ListNode A = headA;ListNode B = headB;//A和B要提前声明，否则后期找不到他们！if(sizeA >sizeB){//A先走差值的步数int countA = sizeA - sizeB;while(countA != 0){A = A.next;countA--;}}else{//B先走int countB = sizeB - sizeA;while(countB != 0){B = B.next;countB--;}}//3.然后让这两个引用各自往后走while(A  != null && B != null){if( A == B){return A;}A = A.next;B = B.next;}return null;}
}

解法1：遍历链表，每次遍历一个节点，就把这个节点的引用存到一个LIst里面，遍历下一个节点的时候，判定下一个节点是否在List中已经存在过了。如果发现某个节点已经在List里面有了，并且又再次遍历到了，认为这个链表是带环的。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//1.首先判断链表是否为空if(head == null){return false;}        //2.创建一个顺序表List<ListNode> list = new ArrayList<>();//3.对链表进行遍历for(ListNode cur = head ; cur != null ;cur = cur.next){//判断一下给的节点的引用是否存在？if(list.contains(cur)){return true;}//如果不存在 那就继续循环list.add(cur);}return false;}
}

然而，上面这种解法的时间复杂度为O（N^2），适合在线笔试的时候用，因为她比较好想。

更好的方法为双指针法：

首先创建两个引用，都指向链表的头部，其中一个引用fast，一次循环，往后走两步

另一个引用slow，一次循环，往后走一步

如果链表不带环，此时这两个引用永远不会重合

如果带环，就会有重合的一天

空间复杂度为O（1），时间复杂度为O（N）（*考虑极端情况，比如环的长度就是整个链表长度N，fast和slow最开始上环的时候，差距是N，此时意味着，每循环一次，差距就措施小N，最多经过N次就重合了）

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//应用双指针法来进行解题//首先判断特殊情况if(head == null){return false;}//创建快慢指针ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){//判断二者是否指向同一个地址if(slow == fast){return true;}fast = fast.next.next;slow = slow.next;}return false;}
}

扩展延申：

当前是fast一次走两步，slow一次走一步，可以判定是否带环

假设fast一次走三步/四步/五步/，slow一次走一步，能否判定出是否带环呢？

结论是否定的。

反例：fast一次走3步，slow一次走1步，环的长度为2，这样的情况下，fast和slow是永远也重合不了的，这和环的长度是有关系的。

规律总结：如果fast和slow的差值为N，此时给长度为N的环，那永远也重合不了~

只有说，fast和slow的差值为1的时候，才是最保险的！

解法：应用快慢指针法来解答这一道题

首先找到slow和fast交汇的位置

创建cur1从交汇位置出发，创建cur2从链表的头部出发，每次循环走一步的方式，同时往后走，当cur1与cur2重合，此时相遇的位置，就相当于环的入口

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//1.首先判断链表是否为空if(head == null){return null;}   //2.然后再使用快慢指针判断有环or无环ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast =fast.next.next;slow = slow.next;//应该在这里进行判断if(fast == slow){break;}}//3.判断是因为哪种情况出来的if(fast ==  null || fast.next == null){return null;}//4.使用cur2，cur1分别从头和相交处开始走ListNode cur2=head;ListNode cur1 =fast;while(cur1 != cur2 ){cur1 = cur1.next;cur2 = cur2.next;}return cur1;}
}

 ArrayList和LinkedList的区别