力扣labuladong——一刷day02

力扣labuladong——一刷day02"/>

力扣labuladong——一刷day02

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、力扣876. 链表的中间结点
• 二、力扣142. 环形链表 II
• 三、力扣160. 相交链表
• 四、力扣141. 环形链表

前言

一、力扣876. 链表的中间结点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode res = new ListNode(-1,head);ListNode p = head;int len = 0;while(p != null){p = p.next;len ++;}int i = len / 2 + 1;p = head;for(int j = 1; j < i; j ++){p = p.next;}return p;}
}

快慢指针遍历一次

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode dump = new ListNode(-1,head);ListNode p1 = dump, p2 = dump;for(; p2 != null;){p1 = p1.next;p2 = p2.next;if(p2 == null){return p1;}p2 = p2.next;}return p1;}
}

二、力扣142. 环形链表 II

/*** 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) {ListNode p1 = head, p2 = head;while(p1 != null && p2 != null && p2.next != null){p1 = p1.next;p2 = p2.next.next;if(p1 == p2){p1 = head;while(p1 != p2){p1 = p1.next;p2 = p2.next;}return p1;}}return null;}
}

三、力扣160. 相交链表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA, p2 = headB;int len1 = 0, len2 = 0;while(p1 != null){len1 ++;p1 = p1.next;}while(p2 != null){len2 ++;p2 = p2.next;}ListNode fast, slow;int edge = 0;if(len1 > len2){edge = len1 - len2;fast = headA;slow = headB;}else{edge = len2 - len1;fast = headB;slow = headA;}while(edge > 0){edge --;fast = fast.next;}while(fast != null && slow != null){if(fast == slow){return fast;}fast = fast.next;slow = slow.next;}return null;}
}

双指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA, p2 = headB;while(p1 != p2){if(p1 == null) p1 = headB;else p1 = p1.next;if(p2 == null) p2 = headA;else p2 = p2.next;}return p1;}
}

四、力扣141. 环形链表

/*** 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) {ListNode p1 = head, p2 = head;while(p1 != null && p2 != null  && p2.next != null){p1 = p1.next;p2 = p2.next.next;if(p1 == p2){return true;}}return false;}
}