当前位置:网站首页>List interview common questions
List interview common questions
2022-07-07 03:49:00 【Come to the pot】
Catalog
1. Remove linked list elements
7. Palindrome structure of linked list
1. Remove linked list elements
link 203. Remove linked list elements - Power button (LeetCode)
Subject requirements
Look at the
Code up
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode prev = head;
ListNode cur = head.next;
while(cur != null) {
if(cur.val == val) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
if (head.val == val) {
head= head.next;
}
return head;
}
}
2. Reverse a linked list
link 206. Reverse a linked list - Power button (LeetCode)
Subject requirements
Look at the
Code up
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;// The chain list is empty
if(head.next == null) return head;// Note that there is only one node
ListNode cur = head.next;
head.next = null;
while(cur != null) {
ListNode curNext= cur.next;
cur.next = head;
head =cur;
cur = curNext;
}
return head;
}
}
3. The middle node of a list
link 876. The middle node of a list - Power button (LeetCode)
Subject requirements
Look at the
Code up
4. Last in the list k Nodes
link Last in the list k Nodes _ Niuke Tiba _ Cattle from (nowcoder.com)
Subject requirements
Look at the
Code up
5. Merge two ordered lists
link 21. Merge two ordered lists - Power button (LeetCode)
Subject requirements
Look at the
Code up
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(-1);// Puppet node Virtual node
ListNode tmp = newHead;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
tmp.next = list1;
list1 = list1.next;
tmp = tmp.next;
} else {
tmp.next = list2;
list2 = list2.next;
tmp = tmp.next;
}
}
if(list1 != null) {
tmp.next = list1;
}
if(list2 != null) {
tmp.next = list2;
}
return newHead.next;
}
}
6. Link list segmentation
link Link list segmentation _ Niuke Tiba _ Cattle from (nowcoder.com)
Subject requirements
Look at the
Code up
import java.util.*;
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
while(cur != null) {
if(cur.val < x) {
// Insert into the first paragraph
if(bs == null) {
// This is the first time to insert an element
bs = cur;
be = cur;
}else {
be.next =cur;
be = be.next;
}
} else {
// Insert into the second paragraph
if(as == null) {
as =cur;
ae =cur;
}else {
ae.next =cur;
ae = ae.next;
}
}
cur = cur.next;
}
if(bs == null) {
return as;
}
be.next =as;
if(as != null) {
ae.next = null;
}
return bs;
}
}
7. Palindrome structure of linked list
link Palindrome structure of linked list _ Niuke Tiba _ Cattle from (nowcoder.com)
Subject requirements
Look at the
Code up
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
if(A == null || A.next == null) {
return true;
}
ListNode fast = A;
ListNode slow = A;
// Find the midpoint
while(fast!= null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// Flip
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// contrast
while(A != slow) {
if(A.val != slow.val) {
return false;
}
// Even number case
if(A.next != slow) {
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}
8. Intersecting list
link 160. Intersecting list - Power button (LeetCode)
Subject requirements
Look at the
Code up
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1. Find the length of two linked lists
int lenA = 0;
int lenB = 0;
ListNode pl = headA;//pl It means to point to the long linked list forever
ListNode ps = headB;//ps Stands for always pointing to a short linked list
while(pl != null) {
lenA++;
pl = pl.next;
}
while(ps != null) {
lenB++;
ps = ps.next;
}
pl = headA;
ps = headB;
//2, Find the difference length of two linked lists len It must be a positive number
int len = lenA -lenB;
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//3. Let the long linked list take the difference length first
while(len != 0) {
pl = pl.next;
len--;
}
//4. Let's go again , meet
while(pl != ps && pl != null) {
pl = pl.next;
ps = ps.next;
}
if(pl == null) {
return null;
}
return pl;
}
}
9. Circular list
link 141. Circular list - Power button (LeetCode)
Subject requirements
Look at the
First , Understand what is a linked list with links ,
By a node in the linked list , Keep looking for next The pointer , It must reach this node again , Such a list is said to have rings , And each node of the linked list with a ring next The pointer , Not for null.
secondly , If you continue to consider using the speed pointer to do this problem , So fast pointer fast Take a few steps at a time ,
(1) If the pointer is fast fast Two steps each time , Slow pointer slow One step at a time , We must meet
(2) If the pointer is fast fast Every time I go 3 Step , go 4 Step ... go n Step , May not meet
So as long as the pointer is fast fast Every time I go 2 Step , The slow pointer goes every time 1 Step , You can definitely catch up , This problem is based on this idea
Code up
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
if(fast == null || fast.next == null) {
return false;
}
return true;
}
}
10. Circular list II
link 142. Circular list II - Power button (LeetCode)
Subject requirements
Look at the
Code up
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) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
slow = head;
while(slow != fast) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
边栏推荐
- About Estimation Statistics
- 23.(arcgis api for js篇)arcgis api for js椭圆采集(SketchViewModel)
- 【安全攻防】序列化與反序列,你了解多少?
- 22.(arcgis api for js篇)arcgis api for js圆采集(SketchViewModel)
- API data interface of A-share index component data
- Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
- Construction of Hisilicon universal platform: color space conversion YUV2RGB
- 编译常量、ClassLoader类、系统类加载器深度探析
- Open3D 网格滤波
- 海思3559万能平台搭建:RTSP实时播放的支持
猜你喜欢
ubuntu20安装redisjson记录
What is Ba? How about Ba? What is the relationship between Ba and Bi?
19.(arcgis api for js篇)arcgis api for js线采集(SketchViewModel)
Adaptive non European advertising retrieval system amcad
Que savez - vous de la sérialisation et de l'anti - séquence?
维护万星开源向量数据库是什么体验
Appx code signing Guide
VHDL实现任意大小矩阵加法运算
How to replace the backbone of the model
QT opens a file and uses QFileDialog to obtain the file name, content, etc
随机推荐
Ubuntu20 installation redisjson record
What is Ba? How about Ba? What is the relationship between Ba and Bi?
Under the tide of "going from virtual to real", Baidu AI Cloud is born from real
我的勇敢对线之路--详细阐述,浏览器输入URL发生了什么
PHP lightweight Movie Video Search Player source code
qt-线程等01概念
codeforces每日5题(均1700)-第七天
Preprocessing - interpolation
图形化工具打包YOLOv5,生成可执行文件EXE
Can the applet run in its own app and realize live broadcast and connection?
QT 项目 表格新建列名称设置 需求练习(找数组消失的数字、最大值)
卡尔曼滤波-1
Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
First understand the principle of network
pip只下载不安装
Confirm the future development route! Digital economy, digital transformation, data This meeting is very important
【mysql】mysql中行排序
Graphical tools package yolov5 and generate executable files exe
R data analysis: how to predict Cox model and reproduce high score articles
Tencent cloud native database tdsql-c was selected into the cloud native product catalog of the Academy of communications and communications