美文网首页
单向链表

单向链表

作者: 水墨小龙虾 | 来源:发表于2017-07-02 22:56 被阅读0次

题目描叙:

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
简单描叙题目意思:
给出了两个非空链表,数据为非负整数。链表倒叙,再相加,逢10进1
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

//Definition for singly-linked list.
 function ListNode(val) {
     this.val = val;
     this.next = null;
 }
 
 /**
  * @param {ListNode} l1
  * @param {ListNode} l2
  * @return {ListNode}
  */
 var addTwoNumbers = function(l1, l2) {
   var sum = l1.val + l2.val;
   var lFirst = new ListNode(sum%10);
   var arg = sum>=10 ? 1 : 0
   var lPrev = lFirst
   l1 = l1.next
   l2 = l2.next;
   while(l1!==null || l2!==null){
     var v1 = l1 === null ? 0: l1.val
     var v2 = l2 === null ? 0: l2.val
     sum = v1+ v2+ arg
     var lMiddle = new ListNode(sum%10)
     arg = sum>=10 ? 1 : 0
     lPrev.next = lMiddle
     lPrev = lMiddle
     if (l1 !== null) l1 = l1.next;
     if (l2 !== null) l2 = l2.next;
   }
   if(arg>0){
     lMiddle = new ListNode(1);
     lPrev.next = lMiddle
   }
   return lFirst
 };

 var a1 = new ListNode(2);
 var a2 = new ListNode(4);
 var a3 = new ListNode(3);
 a1.next = a2;
 a2.next = a3;

 var b1 = new ListNode(5);
 var b2 = new ListNode(6);
 var b3 = new ListNode(4);
 b1.next = b2;
 b2.next = b3;

 var s = addTwoNumbers(a1, b1);
 console.log(s)

单项链表 A->B->C->D->E , 输出 E->D->C->B->A

初始化数据a1

ffunction ListNode(val) {
    this.val = val;
    this.next = null;
    return {
      val:val,
      next:null
    }
}

var a1 = new ListNode('A')
var a2 = new ListNode('B')
var a3 = new ListNode('C')
var a4 = new ListNode('D')
var a5 = new ListNode('E')
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5
1 思路

把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中,就地反转。
dummy->A->B->C->D->E
dummy->B->A->C->D->E
dummy->C->B->A->D->E
dummy->D->C->B->A->E
dummy->E->D->C->B->A

2 过程

pCur是需要反转的节点。
prev连接下一次需要反转的节点
反转节点pCur
纠正头结点dummy的指向
pCur指向下一次要反转的节点

伪代码
prev.next = pCur.next;
pCur.next = dummy.next;
dummy.next = pCur;
pCur = prev.next;
function reverse(list){
  if(list == null){
    return list
  }
  var dummy = ListNode(-1);
  dummy.next = list;
  var prev = dummy.next;
  var pCur = prev.next;
  while(pCur !==null){
    prev.next = pCur.next;
    pCur.next = dummy.next;
    dummy.next = pCur;
    pCur = prev.next;
  }
  return dummy.next
}

相关文章

  • 8.单向链表SingleLinkList

    目录:1.单向链表的定义2.单向链表的图解3.单向链表定义操作4.单向链表的实现 1.单向链表的定义 2.单向链表...

  • 线性表-单向循环链表

    为了方便,本文介绍的单向循环链表不包含头节点 单向循环链表内容 单向循环链表的的定义 单向循环链表的创建 单向循环...

  • 10.单向循环链表SingleCycleLinkList

    目录:1.单向循环链表的定义2.单向循环链表的图解3.单向循环链表定义操作4.单向循环链表的实现 1.单向循环链表...

  • 数据结构与算法——线性表3

    线性表——单向循环链表 3、单向循环链表 在单向链表的基础上,单向链表的尾结点的Next指向链表的头部,就是为循环...

  • 04单向循环链表实现总结

    一、说说什么是单向循环链表? 人狠话不多. 上图. 单向循环链表就是这个样子!单向循环链表.png 与单向链表区别...

  • 数据结构基础--单向循环链表

    单向循环链表 单向循环链表是可循环的单链表,它与单链表的区别在于单向链表的最后一个元素的指针域为空,而单向循环链表...

  • 2019-12-04 Java-LinkedList源码解读

    @TOC 1、链表数据结构 链表分为单向链表和双向链表,他们的区别在于,单向链表只能单向寻址,而双向链表可以双向寻...

  • 数据结构与算法之循环链表(3.4)

    目录 单向循环链表双向循环链表约瑟夫问题如何发挥循环链表的最大威力? 一 单向循环链表 单向循环链表 - 只有一个...

  • day03-双向链表

    双向链表: 单向链表只能单向查找,双向链表可以双向查找。 啥是双向链表? 双向链表可以双向查数据,所以就不存在单向...

  • 链表

    一、单向链表 单向链表的普通实现 Java实现: Kotlin实现: 单向链表的递归实现 Java实现: 二、双向...

网友评论

      本文标题:单向链表

      本文链接:https://www.haomeiwen.com/subject/cwfocxtx.html