Merge Two Sorted Lists

Write an algorithm that merges two sorted lists.

Approach

The general idea to approach this problem is to have two pointers for the two lists. There will be another pointer to iterate through the lists and pick the smaller node of the two pointers at each node and move the current pointer along.

ListNode Definition

public class ListNode {
    int data;
    ListNode next;

    public ListNode(data, next) {
        this.data = data;
        this.next = next;
    }
}

Implementation

public static ListNode merge(ListNode listOne, ListNode listTwo) {
    ListNode pseudoHead = new ListNode(0, null);
    ListNode cur = pseudoHead;

    while (listOne != null && listTwo != null) {
        if (listOne.data < listTwo.data) {
            cur.next = listOne;
            listOne = listOne.next;
        }
        else {
            cur.next = listTwo;
            listTwo = listTwo.next;
        }

        cur = cur.next;
    }

    cur.next = (listOne != null) ? listOne : listTwo;
    return pseudoHead.next;
}

This article is my 33rd oldest. It is 147 words long, and it’s got 0 comments for now.