[解決済み] インタビューの質問です。2つのソートされた単一リンクリストを新しいノードを作成することなくマージする。

質問内容

これは面接のための筆記試験で聞かれたプログラミングの問題である。 あなたは既にソートされた2つの単一連結リストを持っています。それらをマージして、新しいノードを作成せずに新しいリストの先頭を返さなければなりません。返されたリストも同様にソートされている必要があります"。

メソッドのシグネチャは Node MergeLists(Node list1, Node list2)です。

ノードクラスは以下の通りです。

class Node{
    int data;
    Node next;
}

私は多くの解決策を試しましたが、余分なノードを作成しないことは物事をねじ曲げます。助けてください。

以下は、付随するブログのエントリです。 http://techieme.in/merging-two-sorted-singly-linked-list/

どのように解決するのですか？

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}