Description: Enter two incrementally sorted lists and merge the two lists so that the nodes in the new list are still incrementally sorted.

The structure of linked lists

A linked list is different from an array. A linked list is a storage structure in which the reference of the last element points to the next element. Linked lists connect elements with elements through Pointers.

The two linked lists L1 and L2 are shown

Each Node has two parts: val and next. Val is the current data and next is the pointer to the next element. L1 and L2 should be combined and ordered incrementally

Thought: processing linked list, through L1, L2 double Pointers to find the corresponding data, compare the size, output to the new linked list structure

Create a new list Res with Head as virtual node [0, null]

Compare the size of val, the first element in L1 and L2 lists, to get the node with the smallest val, to which the next pointer to Res points

First use JS to create a linked list data structure NodeList

Class NodeList {constructor(val) {this.val = val this.next = null} class NodeList {constructor(val) {this.val = val this.next = null Node = new NodeList(val) while (currnt.next) {currnt = currnt.next} currnt.next = node} // Print print() {let current =  this let res = [] while (current) { res.push(current.val) current = current.next } console.log(res) } }Copy the code

Create 2 linked lists as shown:

let node1 = new NodeList(1) node1.append(2) node1.append(6) node1.append(8) let node2 = new NodeList(3) node2.append(4) Node2.append (5) node2.append(9 // print node1.print() node2.print()Copy the code

Results: [1, 2, 6, 8] [3, 4, 5, 9]

Implementation:

const f = (n1, N2) => {let res = new NodeList(0) // create virtual node let p = res // res pointer let p1 = n1 // L1 pointer let p2 = n2 // L2 pointer while (p1 &&) {if (p1, p2) val < p2. Val) {p.n ext = p1 / / p pointer to p1 p1 = p1. Next / / L1 pointer moves to the right} else {p.n ext = p2 / / pointer to p2 p2 = p P2. next // L2 pointer moved right} p = p.ext // p pointer moved right} p.ext = p1? Return res.next} return res.next} return res.next}Copy the code

The test results

const res = f(node1, node2) res.print()

Output: [1, 2, 3, 4, 5, 6, 8, 9]

Complete code:

Class NodeList {constructor(val) {this.val = val this.next = null} class NodeList {constructor(val) {this.val = val this.next = null Node = new NodeList(val) while (currnt.next) {currnt = currnt.next} currnt.next = node} // Print print() {let current =  this let res = [] while (current) { res.push(current.val) current = current.next } console.log(res) } } const f = (n1, N2) => {let res = new NodeList(0) // create virtual node let p = res // res pointer let p1 = n1 // L1 pointer let p2 = n2 // L2 pointer while (p1 &&) {if (p1, p2) val < p2. Val) {p.n ext = p1 / / p pointer to p1 p1 = p1. Next / / L1 pointer moves to the right} else {p.n ext = p2 / / pointer to p2 p2 = p P2. next // L2 pointer moved right} p = p.ext // p pointer moved right} p.ext = p1? p1 : P2 // There is a list that has been merged, Return res.next} let node1 = new NodeList(1) node1.append(2) node1.append(6) node1.append(8) let node2 = new NodeList(3) node2.append(4) node2.append(5) node2.append(9) node1.print() node2.print() const res = f(node1, node2) res.print()Copy the code

github