Location>code7788 >text

[Ninja Algorithm] From Zipper to Linked List: Exploring the Way to Merge Ordered Linked List｜LeetCode 21 Merge Two Ordered Linked Lists

Popularity：523 ℃/2025-02-19 23:55:23

From Zipper to Linked List: Exploring the merger of ordered linked lists

Merger in life

Imagine you are sorting out two stacks of receipts sorted by date. The most natural way is to pick up two stacks of receipts, compare the top date each time, and select the earlier one and put it in the new stack. This simple daily operation is exactly the true portrayal of the orderly linked list merging issue we are going to discuss today.

Problem description

LeetCode Question 21 "Merge two ordered linked lists" requirements: merge two ascending linked lists into a new ascending linked list and return. A new linked list is composed of all nodes of the given two linked lists.

For example:

Enter: 1 → 2 → 4, 1 → 3 → 4
 Output: 1 → 1 → 2 → 3 → 4 → 4

 Enter: empty list, 0
 Output: 0

 Input: empty linked list, empty linked list
 Output: empty link table

Brutal solution: convert to array sorting

The most intuitive idea might be: put the values ​​of both linked lists into an array, sort them and then create a new linked list. Although this method is not elegant enough, it is very helpful to understand the problem.

Violent solution implementation

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
     // Create an array to store all node values
     List<Integer> values ​​= new ArrayList<>();
    
     // traverse the first linked list
     while (list1 != null) {
         ();
         list1 = ;
     }
    
     // traverse the second linked list
     while (list2 != null) {
         ();
         list2 = ;
     }
    
     // Sort array
     (values);
    
     // Build a new link list
     ListNode dummy = new ListNode(0); // Sentinel node
     ListNode current = dummy;
    
     // Create a new linked table based on the sorted array
     for (int value : values) {
          = new ListNode(value);
         current = ;
     }
    
     return ;
 }

Optimization solution: Double pointer traversal

Since the entered linked list has been sorted, we can completely simulate the process of sorting out receipts: traverse two linked lists at the same time, and select a smaller node to connect to the result linked list each time. This is like a zipper, combining two ordered sequences into one.

Code implementation and detailed explanation

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
     // Create sentinel nodes to simplify boundary situation processing
     ListNode dummy = new ListNode(0);
     ListNode current = dummy;
    
     // When neither linked list is empty, compare and connect
     while (list1 != null && list2 != null) {
         if ( <= ) {
              = list1;
             list1 = ;
         } else {
              = list2;
             list2 = ;
         }
         current = ;
     }
    
     // Process the remaining nodes
     if (list1 != null) {
          = list1;
     }
     if (list2 != null) {
          = list2;
     }
    
     return ;
 }

Graphical process

1) Initial status:
 list1: 1 → 2 → 4
 list2: 1 → 3 → 4
 result: dummy →

 2) After the first comparison:
 list1: 2 → 4
 list2: 1 → 3 → 4
 result: dummy → 1 →

 3) After the second comparison:
 list1: 2 → 4
 list2: 3 → 4
 result: dummy → 1 → 1 →

 4) Final result:
 result: dummy → 1 → 1 → 2 → 3 → 4 → 4

Comparison of complexity

Violent solution:

  • Time complexity: O(nlogn), mainly from the sorting process
  • Space complexity: O(n), need an additional array to store all nodes
  • Disadvantages: No utilizing the sorted feature of linked lists

Double pointer solution:

  • Time complexity: O(n), only need to traverse once
  • Space complexity: O(1), only a few pointers are required
  • Advantages: Make full use of the sorted feature of input linked lists

Skills and thoughts

  1. The wonderful use of sentinel nodes

    • Use sentinel nodes to unify boundary situation processing
    • Avoid special treatment of head nodes

  2. The idea of ​​in-place merger

    • No need to create a new node
    • Merge is achieved by changing the pointer pointer

  3. Process the remaining nodes

    • Directly connect to the remaining link list
    • Avoid continuing to traverse the remaining nodes

Extension of practical application

The idea of ​​merging ordered linked lists is very common in actual development:

  1. Ordered result collection in the database
  2. Merge of ordered files in file system
  3. Log merges sorted by timestamp in the log system

summary

Merging ordered linked lists seems simple, but actually contains important algorithmic ideas:

  1. How to efficiently process ordered data
  2. Pointer operation skills
  3. How to simplify boundary condition processing

Remember: When encountering similar merge problems, first consider whether the data is ordered. If it is ordered, you can often design a more elegant and efficient solution.

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

<Previous Next>