“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Merge sorted linked lists

25. Merge two sorted lists

Topic describes

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

The sample

Example 1

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code

Tip:

  • 0 <= List length <= 1000

Problem solving:

Solution 1: open up a new linked list to merge

Train of thought

Personally, I think the best way to solve linked list problems is to draw a picture, because the pointer points back and forth, easily confused, drawing is the most clear. A merger between the two ordered list, the easiest way is to open a new list, to find a new list of sentinel nodes act as virtual head node, each found in the two lists that a smaller, inserted into the new list, until one of the two list list traversal over, will be another list, the remaining nodes connected to the new list tail. Look at the picture (this solution has high spatial complexity)

It’s pretty simple. I don’t want to paste the code

Solution two: merge in place

Train of thought

  1. First, there are two Pointers to the latest node location of the two lists (curr1, curR2).
  2. Find the smallest of the two list heads and create a new pointer (newHead) to it. And moves its pointer back one bit
  3. Define a move pointer (moveNode) that initially points to the head node with a smaller value
  4. Iterate over the two lists, comparing the node values of the two lists in turn, whose value is smaller, and who is inserted after the move pointer
  5. After traversal, insert the non-empty list remaining node after the move pointer

The text is hard to understand. Look at the picture

code

func MergeLinkList(l1 *LinkList.Node, l2 *LinkList.Node) *LinkList.Node { if l1 == nil && l2 == nil { return nil } if l1 == nil { return l2 } if l2 == nil { Var newHead * linklist. Node if curr1.Data <= curr2.Data {return l1} curr1 := l1 // curr2 := l2 // linklist. Node if curr1.Data <= curr2.Data { newHead = curr1 curr1 = curr1.Next } else { newHead = curr2 curr2 = curr2.Next } moveNode := newHead for ; curr1 ! = nil && curr2 ! = nil; moveNode = moveNode.Next { if curr1.Data < curr2.Data { moveNode.Next = curr1 curr1 = curr1.Next } else { moveNode.Next = curr2 curr2 = curr2.Next } } if curr1 ! = nil { moveNode.Next = curr1 } if curr2 ! = nil{ moveNode.Next = curr2 } return newHead }Copy the code