当前位置:网站首页>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;
}
}
边栏推荐
- pip只下载不安装
- 亚像素级角点检测Opencv-cornerSubPix
- 再AD 的 界面顶部(菜单栏)创建常用的快捷图标
- Implementation steps of docker deploying mysql8
- Set WiFi automatic connection for raspberry pie
- 海思3559万能平台搭建:RTSP实时播放的支持
- 23.(arcgis api for js篇)arcgis api for js椭圆采集(SketchViewModel)
- [untitled]
- Depth analysis of compilation constants, classloader classes, and system class loaders
- The latest 2022 review of "small sample deep learning image recognition"
猜你喜欢
VHDL implementation of arbitrary size matrix multiplication
浅谈网络安全之文件上传
代码质量管理
Open3d mesh filtering
海思万能平台搭建:颜色空间转换YUV2RGB
线性表的查找
10 ways of interface data security assurance
Sub pixel corner detection opencv cornersubpix
【mysql】mysql中行排序
21. (article ArcGIS API for JS) ArcGIS API for JS rectangular acquisition (sketchviewmodel)
随机推荐
The true face of function pointer in single chip microcomputer and the operation of callback function
Top 50 hit industry in the first half of 2022
Calculation of time and space complexity (notes of runners)
【安全攻防】序列化與反序列,你了解多少?
复杂因子计算优化案例:深度不平衡、买卖压力指标、波动率计算
2022年上半年HIT行业TOP50
About Estimation Statistics
About Tolerance Intervals
Construction of Hisilicon universal platform: color space conversion YUV2RGB
QT item table new column name setting requirement exercise (find the number and maximum value of the array disappear)
【C语言】 题集 of Ⅸ
Preprocessing - interpolation
Probability formula
19. (ArcGIS API for JS) ArcGIS API for JS line acquisition (sketchviewmodel)
[Dameng database] after backup and recovery, two SQL statements should be executed
Open3d mesh filtering
Gpt-3 is a peer review online when it has been submitted for its own research
What is the experience of maintaining Wanxing open source vector database
What is Ba? How about Ba? What is the relationship between Ba and Bi?
机器学习笔记 - 使用机器学习进行鸟类物种分类