【算法刷题day4】Leetcode:24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
文章目录
Leetcode 24. 两两交换链表中的节点
题目：24. 两两交换链表中的节点
解析：2.5 练习时长两年半
解题思路
借助虚拟头节点，每次处理后面的节点，三种情况：后面为空、后面只有一个接待你不用做；后面有两个非空节点，调转他们。
代码
/**
* 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 swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode curNode = dummy;
while (curNode.next != null && curNode.next.next != null){
ListNode tmp = curNode.next;
curNode.next = tmp.next;
tmp.next = curNode.next.next;
curNode.next.next = tmp;
curNode = curNode.next.next;
}
return dummy.next;
}
}
总结
暂无
Leetcode 19. 删除链表的倒数第 N 个结点
解题思路
fastIdx先走index步，慢的跟上，然后删除节点
代码
/**
* 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 dummy = new ListNode(-1);
dummy.next = head;
ListNode slowIdx = dummy, fastIdx = dummy;
for (int i = 0; i < n; i++){
if (fastIdx == null)
return dummy.next;
fastIdx = fastIdx.next;
}
while (fastIdx != null && fastIdx.next != null){
fastIdx = fastIdx.next;
slowIdx = slowIdx.next;
}
slowIdx.next = slowIdx.next.next;
return dummy.next;
}
}
总结
题目说index是1到n，所以判断条件冗余了。
可以让fastIdx多走一步，那下面的判断条件可以少一个fast.next!=null
/**
* 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 dummy = new ListNode(-1);
dummy.next = head;
ListNode slowIdx = dummy, fastIdx = dummy;
for (int i = 0; i <= n; i++){
fastIdx = fastIdx.next;
}
while (fastIdx != null){
fastIdx = fastIdx.next;
slowIdx = slowIdx.next;
}
slowIdx.next = slowIdx.next.next;
return dummy.next;
}
}
Leetcode面试题 02.07. 链表相交
题目：面试题 02.07. 链表相交
解析：2.5 练习时长两年半
解题思路
走到相同的起点，一起往后。
代码
/**
* 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 curA = headA;
ListNode curB = headB;
int lengthA = 0;
int lengthB = 0;
while (curA != null){
curA = curA.next;
lengthA++;
}
while (curB != null){
curB = curB.next;
lengthB++;
}
curA = headA;
curB = headB;
for (int i = 0; i < lengthA - lengthB; i++)
curA = curA.next;
for (int i = 0; i < lengthB - lengthA; i++)
curB = curB.next;
while (curA != null){
if (curA == curB)
return curA;
curA = curA.next;
curB = curB.next;
}
return null;
}
}
总结
暂无
Leetcode 142. 环形链表 II
题目：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 slowIdx = head, fastIdx = head;
while (fastIdx != null && fastIdx.next != null) {
slowIdx = slowIdx.next;
fastIdx = fastIdx.next.next;
//第一次相遇
if (slowIdx == fastIdx){
//开始第二次相遇
slowIdx = head;
while (slowIdx != fastIdx){
slowIdx = slowIdx.next;
fastIdx = fastIdx.next;
}
return slowIdx;
}
}
return null;
}
}
总结
暂无
原文地址：https://blog.csdn.net/qq_45022758/article/details/136964211
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！