Append Linked Lists Editorial

Practice Problem Link: Append Linked Lists

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two Linked Lists, append the second Linked List to the end of the first Linked List and return the first list.

Approach

Traverse to the last element of the first list and store the address of the first element of the second list in the next pointer value of the last element of the first list. Return the first list.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* appendLists (ListNode* list1, ListNode* list2) {
    ListNode* currentNode = list1;
	while (currentNode->next != NULL) {
		currentNode = currentNode->next;
	}
	currentNode->next = list2;
	return list1;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/

class Solution {
	ListNode appendLists (ListNode list1, ListNode list2) {
	    ListNode currentNode = list1;
		while (currentNode.next != null) {
			currentNode = currentNode.next;
		}
		currentNode.next = list2;
		return list1;
	}
}