Use Java

Programming Assignment $1$: Alternating Merge of Two Linked Lists

Objective:

Your task is to create a method that merges two singly linked lists into a third linked list. The elements of the original lists should alternate in the new list. That is$,$ the first element of the

merged list should be the first element of the first list, the second element of the merged list should be the first element of the second list, and so on$.$

Requirements:

$1.$ You will implement a method that takes two linked lists as input and returns a new linked

list with elements from both lists, alternating between them.

$2.$ If one of the lists runs out of elements before the other, the remaining elements from the

longer list should be appended to the new list.

$3.$ Use the code we have developed in class as your foundation for this project

Method Signature:

LinkedList mergeAlternating$($LinkedList list$1,$ LinkedList list$2)$;

Special Cases to Consider:

$$ One or both of the input lists could be empty.

$$ The input lists may have different lengths.

Make sure your code handles these cases gracefully and efficiently. Be prepared to discuss the

time and space complexity of your solution.

Deliverables:

$$ Submit your solution code along with a short write$-$up explaining how you handled the

special cases and the overall logic of your approach. Add this part as a comment in the

code itself above the method you are creating.

$$ Ensure that your code is well$-$commented, and any assumptions are clearly stated.

Code use in class:

package linkedlist$2$;

public class LinkedList$2\{$

private Node head, tail;

private int size;

public LinkedList$2()\{$

this$($null$)$;

$\}$

public LinkedList$2($Node node$)\{$

this.head $=$ this.tail $=$ node;

size $=($node $!=$ null$)?1$ : $0$;

$\}$

public int getSize$()\{$

return size;

$\}$

public Node getHead$()\{$

return head;

$\}$

public Node getTail$()\{$

return tail;

$\}$

public void setHead$($Node head$)\{$

this.head $=$ head;

$\}$

public void setTail$($Node tail$)\{$

this.tail $=$ tail;

$\}$

public boolean isEmpty$()\{$

return this.head $==$ null;

$\}$

private void checkNullNode$($Node node$)$ throws Exception$\{$

if $($node $==$ null$)$

throw new Exception$("$Null node"$)$;

$\}$

private void insertFront$($Node node$)$ throws Exception$\{$

checkNullNode$($node$)$;

if $($isEmpty$())$

tail $=$ node;

node.setNext$($this$.$head$)$;

head $=$ node;

size$++$;

$\}$

$//?????$

public boolean move$($int index$1,$ int index$2)\{$

return true;

$\}$

private void insertEnd$($Node node$)$ throws Exception$\{$

checkNullNode$($node$)$;

if $($isEmpty$())$

insertFront$($node$)$;

else$\{$

tail.setNext$($node$)$;

tail $=$ node;

size$++$;

$\}$

$\}$

public void insert$($int data, int index$)$ throws Exception$\{$

insert$($new Node$($data$),$ index$)$;

$\}$

public void insert$($Node node, int index$)$ throws Exception$\{$

checkNullNode$($node$)$;

Node curr $=$ head;

int currIndex $=0$;

if $($isEmpty$())$

insertFront$($node$)$;

else$\{$

if $($index $<=0)$

insertFront$($node$)$;

else if $($index $>=$ size$)$

insertEnd$($node$)$;

else$\{$

while $($currIndex $<$ index $-1)\{$

curr $=$ curr.getNext$()$;

currIndex$++$;

$\}$

node $=$ curr.getNext$()$;

curr.setNext$($node$)$;

size$++$;

$\}$

$\}$

$\}$

public boolean removeIndex$($int index$)\{$

if $($isEmpty$()||$ index $<0||$ index $>=$ size$)$

return false;

else if$($size $==1)\{$

head $=$ tail $=$ null;

size$--$;

return true;

$\}$

else if $($index $==0)\{$

head $=$ head.getNext$()$;

size$--$;

return true;

$\}$

else $\{$

Node curr $=$ head;

int currIndex $=0$;

while $($currIndex $<$ index $-1)\{$

curr $=$ curr.getNext$()$;

currIndex$++$;

$\}$

curr.setNext$($curr$.$getNext$().$getNext$())$;

size$--$;

return true;

$\}$

$\}$

public boolean removeData$($int data$)\{$

Node curr $=$ head;

int currIndex $=0$;

if $($isEmpty$())$

return false;

else $\{$

while $($curr$.$getData$()!=$ data$)\{$

curr $=$ curr.getNext$()$;

if $($curr $==$ null$)$

return false;

currIndex$++$;

$\}$

$\}$

return removeIndex$($currIndex$)$;

$\}$

public boolean removeD