找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4620|回复: 12
收起左侧

[米群网刷题小分队] [LeetCode] LinkedList 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-8-2014 07:00 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-13-2014 06:01 PM 编辑

Add Two Numbers

思路:
由于是逆序存储,可以直接从链表头加到链表尾。
当l1或者l2不全为空的时候,进入正常的加法处理。
直到l1,l2全为空的时候,检查carry是否为0,不为0 的话需要在结果链表的结尾append一个节点。

复杂度:
时间 O(max(m,n)) 假设m,n 分别是l1, l2的长度。
空间 O(1) 如果结果空间也算就是O(n), O(1)是说只考虑程序运行时占用的临时空间大小。

错误:
1. while loop 里计算完忘记了 l1 = l1.next; 这个错误会导致TLE。
2. l1没有check null就直接l1 = l1.next了。null pointer exception

  1. public class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
  4.         ListNode dummy = new ListNode (-1);
  5.         ListNode cur = dummy;
  6.         int carry = 0;
  7.         while(l1 != null || l2 != null)
  8.         {
  9.             int num1 = l1 != null ? l1.val : 0;
  10.             int num2 = l2 != null ? l2.val : 0;
  11.             int digit = num1 + num2 + carry;
  12.             carry = digit/10;
  13.             digit = digit%10;
  14.             cur.next = new ListNode(digit);
  15.             cur = cur.next;
  16.             l1 = l1 != null ? l1.next: null; //TLE if missing, NullPointerException if do not check null.
  17.             l2 = l2 != null ? l2.next : null;
  18.         }
  19.         if(carry != 0)
  20.         {
  21.             ListNode c = new ListNode(carry);
  22.             cur.next = c;
  23.         }
  24.         return dummy.next;
  25.     }
  26. }
复制代码

Follow up, 如果是正向存储呢?
cc 150上有。

1. 一个保底解法是 先把两个链表reverse再相加。2. cc 150上给的官方解法, 先padding, 感觉略麻烦啊。。

本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 05:55 PM | 显示全部楼层
Intersection of Two Linked Lists

思路:
这个题目貌似是一道原题。
一共扫三次,前两次查链表A和B的长度。然后把长的那个提前走|lenA - lenB|步。这样同时遍历A和B,如果A,B 当前节点相同了。证明是intersection点。
时间是 O(3*n) -> O (n), 空间是O(1)

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         if(headA == null || headB == null) return null;
  4.         ListNode curA = headA;
  5.         ListNode curB = headB;
  6.         int lenA = 0;
  7.         int lenB = 0;
  8.         while(curA !=null)
  9.         {
  10.             curA = curA.next;
  11.             lenA ++;
  12.         }
  13.         while(curB !=null)
  14.         {
  15.             curB = curB.next;
  16.             lenB ++;
  17.         }
  18.         int dif = Math.abs(lenA - lenB);
  19.         boolean movesA = lenA > lenB ? true : false;
  20.         curA = headA;
  21.         curB = headB;
  22.         while(dif > 0)
  23.         {
  24.             if(movesA) curA = curA.next;
  25.             else curB = curB.next;
  26.             dif --;
  27.         }
  28.         while(curA != null || curB != null)
  29.         {
  30.             if(curA == curB) return curA;
  31.             else
  32.             {
  33.                 curA = curA.next;
  34.                 curB = curB.next;
  35.             }
  36.         }
  37.         return null;
  38.     }
  39. }
复制代码


发表于 12-9-2014 10:50 AM | 显示全部楼层
MengMa 发表于 12-9-2014 10:42 AM
如果链表节点是正向存储的话, 有什么比较巧妙的解法吗?

正反有关系么。。。
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-9-2014 11:11 AM | 显示全部楼层
cpcs 发表于 12-9-2014 10:50 AM
正反有关系么。。。

反向是低位存链表头,可以l1, l2一路加到尾部,不用管两个链表长度是否相同。
正向是高位存链表头,好像还要给俩链表长度对齐补0啥的。感觉很繁琐。

或者我就干脆先reverse链表再做。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表