合并两个排序的链表
题目描述
思路
双指针
自己想的,就普通的双指针,结构化讨论
对于第一个节点的确定,自己的思路没问题,提供一种其他思路,用一个伪头节点
代码实现
双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)return l2;
if(l2==null)return l1;
ListNode result=l1;
ListNode cur1=l1,cur2=l2;
while(cur1!=null&&cur2!=null){
if(cur1.val<=cur2.val){
while(cur1.next!=null &&cur1.next.val<=cur2.val){
cur1=cur1.next;
}
ListNode tmp1 = cur1.next,tmp2 = cur2.next;
cur1.next=cur2;
cur2.next=tmp1;
cur2=tmp2;
}else{
result=l2;
while(cur2.next!=null && cur2.next.val<=cur1.val){
cur2=cur2.next;
}
ListNode tmp2 = cur2.next;
cur2.next=cur1;
cur2=tmp2;
}
}
return result;
}
}
复杂度分析
时间复杂度
O(M+N)
空间复杂度
O(1)
反思不足
思路
对于节点调用next域的时候一定要判断是否为空
两个链表的第一个公共节点
题目描述
思路
正难则反
从尾往头找最后一个相同的节点
需要两次逆置
本题并不行,需要保证原有结构
Set集合
第一个添加失败的节点就是结果
需要哈希表
利用数量关系
遍历A一次后再遍历B一次与反过来遍历的次数是一样的,且公共尾部出现的时机也是一样的
a不等于b,但是a+b会等于b+a,且公共尾部会重合
代码实现
正难则反
Set集合
利用数量关系
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a=headA,b=headB;
while(a!=b){
a=a!=null?a.next:headB;
b=b!=null?b.next:headA;
}
return a;
}
}
复杂度分析
时间复杂度
均为O(M+N)
空间复杂度
哈希表为O(M+N),其他均为O(1)
反思不足
思路
多从数学的量的关系来想题
审题
标签:ListNode,val,offer,复杂度,next,day12,l1,null From: https://www.cnblogs.com/zhouj-learn/p/16799712.html题目要求不能改变原结构