本文主要是介绍力扣算法学习day03-3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 力扣算法学习day03-3
- 19-删除链表的倒数第N个结点
-
- 面试题02.07.-链表相交
-
- 142-环形链表II
-
力扣算法学习day03-3
19-删除链表的倒数第N个结点
题目
代码实现
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode node = new ListNode(0,head);
ListNode pre = node;
ListNode cur = node;
while(n-- >= 0){
cur = cur.next;
}
while(cur != null){
pre = pre.next;
cur = cur.next;
}
pre.next = pre.next.next;
return node.next;
}
}
面试题02.07.-链表相交
题目
代码实现
/**
* 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) {
int lengthA = 0;
int lengthB = 0;
ListNode nodeA = headA;
ListNode nodeB = headB;
// 首先计算两个链表的长度
while(nodeA != null){
nodeA = nodeA.next;
lengthA++;
}
while(nodeB != null){
nodeB = nodeB.next;
lengthB++;
}
// 由于哪个长不确定,可以在思维上认为headA是更长的那个,并在判断后将headA指向长链表的头结点。
// 顺带将长度之差求得。
int length = 0;
if(Math.max(lengthA,lengthB) == lengthA){
nodeA = headA;
nodeB = headB;
length = lengthA - lengthB;
} else {
nodeA = headB;
nodeB = headA;
length = lengthB - lengthA;
}
// 然后将nodeA指针移动到尾部长度对齐位置。
while(length > 0){
nodeA = nodeA.next;
length--;
}
// 对齐后,开始寻找交点
while(nodeA != null){
// 注意,这里判断的是结构,即指针,而不是值。
if(nodeA == nodeB){
return nodeA;
}
nodeA = nodeA.next;
nodeB = nodeB.next;
}
return null;
}
// 力扣评论区大佬超简洁代码
// 注:他这个方法的话,其实就是利用这个结构本身,两个指针一起走,短的链表先走完,然后把这个指针放在长的链表头上,
// 然后继续两个指针一起走,当长的走到底后,同样的,放到短链表头上,这时,两个指针到结尾的长度就相等了,就可以开始
// 寻找相交点了。
// public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// ListNode h1 = headA, h2 = headB;
// while (h1 != h2) {
// h1 = h1 == null ? headB : h1.next;
// h2 = h2 == null ? headA : h2.next;
// }
// return h1;
// }
}
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) {
/*
思路参考代码随想录,很棒。
设入口距为x,相遇点退回入口的距离为y,相遇点经过环到入口距离为z
慢指针到相遇点距离:x + y
快指针到相遇点距离:x + y + n(y + z)
慢指针速度为快指针的一半,故 2(x + y) = x + y + n(y + n)
上式变形:x = (n - 1)(y + z) + z
其中y + z为环形一圈,所以,去掉重复的圈数,则x = z
故从距离上看,头结点到入口结点和相遇结点经环到入口结点的距离相同。
*/
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
// 找到相遇结点
while(true){
// 没有环,则返回null
if(fast.next == null || fast.next.next == null){
return null;
}
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
break;
}
}
// 使slow重新指向头结点
slow = head;
// 找到入口结点
while(true){
if(fast == slow){
return fast;
}
slow = slow.next;
fast = fast.next;
}
}
}
这篇关于力扣算法学习day03-3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!