Scribd
Upload
9 views3 pages

LinkedList Merge Problem Java

The document provides a Java implementation for merging two linked lists that share a common point. It includes classes for ListNode and NumberChainUtils, which contains methods to find the merge point, calculate lengths before merging, and append the shorter chain to the longer one. Additionally, it includes a test class to verify the functionality of the merging process.

Uploaded by

HRITHIK SINGH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views3 pages

LinkedList Merge Problem Java

The document provides a Java implementation for merging two linked lists that share a common point. It includes classes for ListNode and NumberChainUtils, which contains methods to find the merge point, calculate lengths before merging, and append the shorter chain to the longer one. Additionally, it includes a test class to verify the functionality of the merging process.

Uploaded by

HRITHIK SINGH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Linked List Merge and Append Problem - Java Implementation

[Link]

package user;

public class ListNode {


public int val;
public ListNode next;

public ListNode(int x) {
val = x;
next = null;
}
}

[Link]

package user;

public class NumberChainUtils {

public static ListNode getMergePoint(ListNode headA, ListNode headB) {


if (headA == null || headB == null) return null;

ListNode a = headA;
ListNode b = headB;

while (a != b) {
a = (a == null) ? headB : [Link];
b = (b == null) ? headA : [Link];
}
return a;
}

public static int getLengthBeforeMerge(ListNode head, ListNode merge) {


int count = 0;
ListNode current = head;
while (current != null && current != merge) {
count++;
current = [Link];
}
return count;
}

public static ListNode appendChain(ListNode longerHead, ListNode shorterHead, ListNode merge)


{
ListNode dummy = new ListNode(0);
ListNode temp = dummy;
ListNode current = shorterHead;
Linked List Merge and Append Problem - Java Implementation

while (current != merge) {


[Link] = new ListNode([Link]);
temp = [Link];
current = [Link];
}

ListNode tail = longerHead;


while ([Link] != null) {
tail = [Link];
}
[Link] = [Link];

return longerHead;
}

public static ListNode solve(ListNode chain1, ListNode chain2) {


ListNode merge = getMergePoint(chain1, chain2);
if (merge == null) return null;

int len1 = getLengthBeforeMerge(chain1, merge);


int len2 = getLengthBeforeMerge(chain2, merge);

if (len1 < len2) {


return appendChain(chain2, chain1, merge);
} else {
return appendChain(chain1, chain2, merge);
}
}
}

[Link]

package user;

import [Link];
import static [Link].*;

public class MixedChainsTest {

@Test
public void testMergeAndAppendSmallerChain() {
ListNode common = new ListNode(8);
[Link] = new ListNode(10);

ListNode a = new ListNode(1);


[Link] = new ListNode(2);
[Link] = new ListNode(3);
[Link] = common;
Linked List Merge and Append Problem - Java Implementation

ListNode b = new ListNode(4);


[Link] = new ListNode(5);
[Link] = common;

ListNode result = [Link](a, b);

int[] expected = {1, 2, 3, 8, 10, 4, 5};


int i = 0;
ListNode current = result;
while (current != null && i < [Link]) {
assertEquals(expected[i++], [Link]);
current = [Link];
}
assertNull(current);
}
}

You might also like