行业知识
算法——链表王
��表刷题详解
203.移除链表元素
力扣题目链接(opens new window)
题意:删除链表中等于给定值 val 的所有节点。
示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
示例 2: 输入:head = [], val = 1 输出:[]
示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]
/** * 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 removeElements(ListNode head, int val) { ListNode dummy =new ListNode(-1); dummy.next=head; ListNode cur =head; ListNode pre =dummy; while( cur != null){ if(cur.val ==val){ pre.next=cur.next; }else{ pre=cur; } cur =cur.next; } return dummy.next; }} 删除时需要知道前面一个节点和当前节点,如果不等于只需 pre =cur 就可以了,cur =cur.next则是等于不等于都要执行的。
707.设计链表
力扣题目链接(opens new window)
题意:
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
class LinkNode{ int val; LinkNode next; LinkNode(){} LinkNode(int val){ this.val =val; }}class MyLinkedList { int size; LinkNode head; public MyLinkedList() { size =0; head = new LinkNode(0); } public int get(int index) { if(indexsize-1) return -1; LinkNode cur=head.next; while(index>0){ cur=cur.next; index--; } return cur.val; } public void addAtHead(int val) { LinkNode newNode = new LinkNode(val); newNode.next=head.next; head.next=newNode; size++; // LinkNode cur =head.next; // LinkNode pre =head; // LinkNode valNode =new LinkNode(val); // valNode.next=cur; // pre.next=valNode; // size++; } public void addAtTail(int val) { LinkNode tmp = head; LinkNode newNode =new LinkNode(val); while(tmp.next !=null){ tmp=tmp.next; } tmp.next=newNode; newNode.next=null; size++; } public void addAtIndex(int index, int val) { if (index > size) { return; } if (index 0){ pre=pre.next; cur=cur.next; index--; } newNode.next= cur; pre.next= newNode; size++; } public void deleteAtIndex(int index) { if (index = size) { return; } LinkNode pre = head; LinkNode cur = head.next; while(index>0){ index--; pre= pre.next; cur=cur.next; } pre.next=cur.next; size--; }}PS:要学会定义链表
206.反转链表
力扣题目链接(opens new window)
题意:反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->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 reverseList(ListNode head) { ListNode pre =null; ListNode cur =head; ListNode tmp; while(cur !=null){ tmp =cur.next; cur.next= pre; pre =cur ; cur =tmp; } return pre; }}PS:无需虚拟头结点,直接操作即可,需要一个tmp来保存当前的下一个节点,本来null在最后面,反转后要在最前面
24. 两两交换链表中的节点
力扣题目链接(opens new window)
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
/** * 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,head); ListNode cur =dummy; ListNode firstNode ; ListNode secondNode ; ListNode tmp; while(cur.next!=null && cur.next.next !=null){ tmp =cur.next.next.next; firstNode =cur.next; secondNode = cur.next.next; cur.next= secondNode; secondNode.next=firstNode; firstNode.next=tmp; cur=firstNode; } return dummy.next; }}PS:做这种交换节点最好要画图,这题需要虚拟头结点,和上一题不同的是,这题需要返回第一个节点的值,就是dummy.next,而上一题反转链表后的第一个节点就是NULL.cur=firstNode中因为second和first已经换过位置了,所以相当于cur前进了两个,因为用到了cur.next.next.next;,所以要保证cur.next.next不为null,当然前提是cur.next不为null
删除链表的倒数第N个节点
力扣题目链接(opens new window)
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2:
输入:head = [1], n = 1 输出:[] 示例 3:
输入:head = [1,2], n = 1 输出:[1]
/** * 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,head); ListNode fastNode=dummy; ListNode slowNode=dummy; while(n>0){ fastNode=fastNode.next; n--; } fastNode=fastNode.next; while(fastNode!=null ){ fastNode=fastNode.next; slowNode=slowNode.next; } slowNode.next=slowNode.next.next; return dummy.next; } }PS:寻找倒数节点时可以使用双指针的方法
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的,但要注意一些细节。
分为如下几步:
- 首先这里我推荐大家使用虚拟头结点,这样方便处理删除实际头结点的逻辑,如果虚拟头结点不清楚
- 定义fast指针和slow指针,初始值为虚拟头结点,如图:
- fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作),如图:
- fast和slow同时移动,直到fast指向末尾,如题:
- 删除slow指向的下一个节点,如图:
面试题 02.07. 链表相交
同:160.链表相交
力扣题目链接(opens new window)
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
示例 2:
示例 3:
/** * 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 cur1=headA; ListNode cur2=headB; int lenA =0; int lenB =0; while(cur1!=null){ cur1=cur1.next; lenA++; } while(cur2!=null){ cur2=cur2.next; lenB++; } ListNode tmpA =headA; ListNode tmpB =headB; if(lenA>lenB){ int n =lenA -lenB; while(n>0){ tmpA=tmpA.next; n--; } }else{ int n =lenB -lenA; while(n>0){ tmpB=tmpB.next; n--; } } while(tmpA!=null){ if(tmpA==tmpB) return tmpA; tmpA=tmpA.next; tmpB=tmpB.next; } return null; }}PS:这题较为简单,因为比的是地址,所以不用考虑值相等而非地址相等的情况,可以先分别算出两个链表的长度,让长的链表先移动长度之差的距离,然后再一一判断两个指针是否相等,注意if(tmpAtmpB) return tmpA;要放在一开始就执行,因为公共节点可能是移动后的第一个节点
142.环形链表II
力扣题目链接(opens new window)
题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
思路是定义一个快指针移动2个单位,定义一个慢指针每次移动一个单位,如果最后快指针与慢指针相等,则可以判断有环,若最后快指针指向了null,则证明该链表没有环了,接下来判断入环的第一个节点,需要使用数学的方法
如果有环,如何找到这个环的入口
此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:
那么相遇时: slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针, (y+z)为 一圈内节点的个数A。
因为fast指针是一步走两个节点,slow指针一步走一个节点, 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2:
(x + y) * 2 = x + y + n (y + z)
两边消掉一个(x+y): x + y = n (y + z)
因为要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。
所以要求x ,将x单独放在左面:x = n (y + z) - y ,
再从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。
先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。
当 n为1的时候,公式就化解为 x = z,
这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。
让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。
动画如下:
那么 n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点。
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow =head; while(fast!=null && fast.next !=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ ListNode tmp2 =fast; ListNode tmp = head; while(tmp!=tmp2){ tmp2=tmp2.next; tmp= tmp.next; } return tmp; } } return null; }}ListNode fast = head; ListNode slow =head; while(fast!=null && fast.next !=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ ListNode tmp2 =fast; ListNode tmp = head; while(tmp!=tmp2){ tmp2=tmp2.next; tmp= tmp.next; } return tmp; } } return null;}}
上一篇:易语言关闭进程线程秘籍,深度解析关闭进程中的线程方法
下一篇:服务器怎么注册微信?