DAY4● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

您所在的位置：网站首页 › 删除链表中的倒数第n个节点 › DAY4● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

DAY4● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

2024-07-13 14:26| 来源: 网络整理| 查看: 265

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

在这里插入图片描述

class Solution { public ListNode swapPairs(ListNode head) { ListNode dummyHead=new ListNode(0);//定义新的节点 dummyHead.next=head;//这个节点就是虚拟头节点 ListNode temp=dummyHead;//定义temp储存虚拟头节点位置 while(temp.next!=null&&temp.next.next!=null){//判断边界：当虚拟头节点的下一个不是空的（偶数个），并且下下一个也不是空的（奇数个） ListNode node1=temp.next;//把1存储下来为node1 ListNode node2=temp.next.next;//把2存储下来为node2 temp.next=node2;//开始交换，第一步 node1.next=node2.next;//第二步 node2.next=node1;//第三步 temp=node1;//将temp指向1，（交换之后1在3之前） } return dummyHead.next; } } 19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作） class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head);//定义新的节点 ListNode first = dummy;//快指针 ListNode second = dummy;//慢指针 for (int i = 0; i lenA){ int tmplen = lenA; lenA =lenB; lenB = tmplen; ListNode tmpNode = curA; curA = curB; curB = tmpNode; } //求长度差 int gap =lenA - lenB; //将curA和curB在同一起点上（末尾位置对齐） while(gap-->0){ curA=curA.next; } //遍历curA和curB，遇见相同则直接返回 while(curA != null){ if(curA == curB){ return curA; } curA = curA.next; curB = curB.next; } return null; } } 142.环形链表II

题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

考察对链表的操作，而且还需要一些数学运算。主要考察两知识点：判断链表是否环如果有环，如何找到这个环的入口

现在看了答案觉得挺有道理的

/** * 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 slow = head; ListNode fast = head; while(fast !=null && fast.next != null){ slow = slow.next;//让快指针每次走两步，慢指针每次走一步，如果有环的话，相对速度为1，快指针肯定能追上 fast = fast.next.next; if(slow == fast){//有环 ListNode index1 = fast; ListNode index2 = head; //定义了两个新指针，从头节点和相遇节点，各走一步，直到相遇，相遇点即为环的入口 while(index1 != index2){ index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }

【本文地址】

DAY4● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

DAY4● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

今日新闻

推荐新闻