当前位置:网站首页>Leetcode-02 (linked list question)
Leetcode-02 (linked list question)
2022-07-07 03:12:00 【Fairy wants carry】
Iterative method :
Ideas : Divide a local location , Then use an auxiliary node and auxiliary pointer , Compare the size and then connect the auxiliary pointer , Push back every time ;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// Auxiliary iteration method
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode help=new ListNode(-1);
ListNode pre=help;// Auxiliary pointer
// Traverse
while (l1 != null && l2 != null){
if(l1.val<=l2.val){
// Connect
pre.next=l1;
pre=pre.next;
l1=l1.next;
}else{
pre.next=l2;
pre=pre.next;
l2=l2.next;
}
}
// Connect the remaining nodes directly
if(l1!=null){
pre.next=l1;
}
if(l2!=null){
pre.next=l2;
}
return help.next;
}
}
The recursive method
class Solution {
// recursive
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1. The end condition
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
//2. Recursive thinking
if(l1.val<=l2.val){
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
The recursive method , Similar to the above
class Solution {
// recursive
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//1. The end condition
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
//2. Recursive thinking
if(list1.val<=list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
}
}
Iterative method
Pay attention to the use of pointer pointing head, Then point to the previous node , Push back slowly
/**
* 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;
// Each cycle is exchanged in pairs
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
Speed pointer :
/**
* 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 middleNode(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
++n;
cur = cur.next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur.next;
}
return cur;
}
}
边栏推荐
- mos管实现主副电源自动切换电路,并且“零”压降,静态电流20uA
- Introduction to ins/gps integrated navigation type
- 腾讯云原生数据库TDSQL-C入选信通院《云原生产品目录》
- Uniapp adaptation problem
- How does C language (string) delete a specified character in a string?
- leetcode
- 安装 torch 0.4.1
- input_delay
- SQL Tuning Advisor一个错误ORA-00600: internal error code, arguments: [kesqsMakeBindValue:obj]
- Detailed explanation of 19 dimensional integrated navigation module sinsgps in psins (filtering part)
猜你喜欢
Use of promise in ES6
制作(转换)ico图标
Redis introduction complete tutorial: replication principle
How-PIL-to-Tensor
Cryptography series: detailed explanation of online certificate status protocol OCSP
mos管实现主副电源自动切换电路,并且“零”压降,静态电流20uA
Nuggets quantification: obtain data through the history method, and use the same proportional compound weight factor as Sina Finance and snowball. Different from flush
QT Bluetooth: qbluetooth DeviceInfo
OC, OD, push-pull explanation of hardware
C language exercises_ one
随机推荐
如何分析粉丝兴趣?
Data analysis from the perspective of control theory
ERROR: Could not find a version that satisfies the requirement xxxxx (from versions: none)解决办法
Jerry's broadcast has built-in flash prompt tone to control playback pause [chapter]
杰理之关于 DAC 输出功率问题【篇】
Lingyun going to sea | yidiantianxia & Huawei cloud: promoting the globalization of Chinese e-commerce enterprise brands
netperf 而网络性能测量
Form validation of uniapp
[2022 national tournament simulation] polygon - computational geometry, binary answer, multiplication
mos管實現主副電源自動切換電路,並且“零”壓降,靜態電流20uA
Laravel php artisan 自动生成Model+Migrate+Controller 命令大全
Detailed explanation of 19 dimensional integrated navigation module sinsgps in psins (filtering part)
Redis introduction complete tutorial: replication principle
uniapp的表单验证
知识图谱构建全流程
Unity使用MaskableGraphic画一条带箭头的线
unrecognized selector sent to instance 0x10b34e810
QT Bluetooth: qbluetooth DeviceInfo
Es6中Promise的使用
cocos3——8.实现初学者指南