merge_sorted_linked_list_followup.js

//   merge two sorted linked list，lc原题.
// 只是又问了两个follow up，一个是去除重复元素merge怎么做，另一个是merge的时候不算重复的数字怎么做
  
//   //initialize
//   dummyhead 
//   head = dummyhead
  
//   pre = null
  
//   //move next
//   pre = head
//   head.next = xxxx

//   //delete
//   pre.next = null;
//   head = pre;

//   //remember duplicate
//   duplicate
  
  
function Node(val){
  this.val = val
  this.next = null
}

var a = new Node(1)
var b = new Node(2)
var c = new Node(2)
a.next = b
b.next = c

var d = new Node(2)
var e = new Node(3)
d.next = e

console.log(merge(a, d)) //=>1,3

function merge(A, B){
  if(A === null && B === null) return null
  var dummy = new Node(null)
  var cur = dummy
  while(A !== null && B !== null){
    if(A.val < B.val){
      cur.next = A
      A = A.next
    }else{
      cur.next = B
      B = B.next
    }
    cur = cur.next
  }
  if(A !== null){
    cur.next = A
  }
  if(B !== null){
    cur.next = B
  }
  //console.dir(dummy.next)
  //remove duplicate
  var ahead = dummy.next
  var behind = dummy
  while(ahead !== null && ahead.next !== null){
    
    if(ahead.val === ahead.next.val){
      while(ahead !== null && ahead.next !== null && ahead.val === ahead.next.val){
        ahead = ahead.next
      }
      behind.next = ahead.next
      ahead = behind.next
    }else{
      ahead = ahead.next
      behind = behind.next
    }
  }
  
  return dummy.next
}

function merge(A, B){
  if (A === null && B === null) return null
  var dummy = new Node(null)
  var cur = dummy
  var before, currDuplicate
  while (A !== null && B !== null){
    var newNode
    if(A.val < B.val){
      newNode = A
      A = A.next;
    }else{
      newNode = B
      B = B.next;
    }
    helper();
  }
  //en
  var newNode = null
  if (A !== null){
    newNode = A
  }
  else if (B !== null){
    newNode = B
  }
  if (newNode !== null) {
    if (cur === null) {
      cur = before;
    }
    while (newNode !== null) {
      helper();
      newNode = newNode.next; 
    }
  }

  
  return dummy.next
  
  function helper(){
      if (newNode.val === cur.val) {
        //new duplicate
        currDuplicate = newNode.val
        //delete curr
        before.next = null;
        //will this work?
        //you are reassign value to cur
        //so in the memory, cur points to different things
        cur = before;
      }
      else if (newNode.val !== currDuplicate) {
        cur.next = newNode;
        before = cur;
        cur = cur.next;
      }
  }
}

function merge(A, B){
  if (A === null && B === null) return null
  var dummy = new Node(null)
  var cur = dummy
  var before, currDuplicate
  while (A !== null || B !== null){
    var newNode
    if(A === null || (B !== null && B.val < A.val)){
      newNode = B
      B = B.next
    }
    else {
      newNode = A
      A = A.next
    }
    if (newNode.val === cur.val) {
      //new duplicate
      currDuplicate = newNode.val
      //delete curr
      
      //won't it be a problem when before and cur is the same pointer?
      //I don't think so, because before is only used to delete a duplicate node when it first occured. hen before and cur point to the same node, we don't need to delete any more nodes, so we won't access the pointer before, thus it won't matter. we won't delete any cur node until a new node is added to the result, in which case before and cur get updated so they won't point at the same node
      before.next = null;
      cur = before;
    }
    else if (newNode.val !== currDuplicate) {
      cur.next = newNode;
      before = cur;
      cur = cur.next;
    }
  }
  return dummy.next
}