力扣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;}
}
更多推荐
力扣labuladong——一刷day02
发布评论