Reverse the Segment Solution || Reverse in Single Linked List || Reverse in Single Linked List From A Specific Position

 Reverse the Segment:

You are given the head of a singly linked list A of length N. The values in the list are A1​,A2​,…,AN​ respectively. You are also given two integers L and R. You need to reverse the nodes of the list from position L to position R.

Input Format

• The first line contains three space-separated integers N, L and R.

• The second line  contains N space-separated integers A1​,A2​,…,AN​.

Output Format

• The output line prints the  nodes from the appropriate segment that are reversed separated by space.

Constraints:

• 1 ≤ N ≤ 10⁵
• $1\le L\le R\le N$
• 1 ≤ Ai ​≤ 10⁹ for each valid i
• the sum of N over all test cases does not exceed 2⋅10⁵ 

^{Sample Input:}

^{6 2 5}

^{1 2 3 4 5 6}

^{Sample Output:}

^{1 5 4 3 2 6}

^Explanation:

^{After reversing the segment [2,5] of the list , the order of the alues is 1,5,4,3,2,6}

 

 

SAMPLE INPUT

 

6 2 5
1 2 3 4 5 6

SAMPLE OUTPUT

 

1 5 4 3 2 6

*(Note do the program in Python 3)*

Program:

class Node:

def __init__(self, data):

self.data = data

self.next = None

def insertEnd(head, data):

newNode = Node(data)

if head is None:

head = newNode

return head

curr = head

while curr.next:

curr = curr.next

curr.next = newNode

return head

def reverseList(head, L, R):

if head is None or head.next is None:

return head

curr = head

prev = None

count = 1

while curr and count < L:

prev = curr

curr = curr.next

count += 1

tail = curr

newTail = None

while curr and count <= R:

nextNode = curr.next

curr.next = newTail

newTail = curr

curr = nextNode

count += 1

tail.next = curr

if prev is None:

head = newTail

else:

prev.next = newTail

return head

def printList(head):

while head:

print(head.data, end=" ")

head = head.next

print()

if __name__ == '__main__':

N, L, R = map(int, input().split())

head = None

for data in map(int, input().split()):

head = insertEnd(head, data)

head = reverseList(head, L, R)

printList(head)

Explanation:

        This code defines a singly linked list and implements a function to reverse a sublist within the linked list.

        The Node class defines a node with a data attribute and a next attribute that points to the next node in the list. The insertEnd function inserts a new node with the given data at the end of the linked list. If the list is empty, the new node becomes the head of the list.

        The reverseList function takes three arguments: the head of the linked list and the starting and ending indices L and R of the sublist to be reversed. The function first traverses the list until it reaches the node at index L, keeping track of the previous node prev, current node curr, and the tail node tail of the sublist to be reversed. It then reverses the sublist by iteratively reversing the next pointers of the nodes within the sublist. Finally, it updates the next pointers of the tail node to point to the node immediately after the sublist, and links the reversed sublist back into the list by updating the next pointer of prev if it exists, or updating the head pointer if the sublist starts at the head.

        The printList function simply traverses the linked list and prints the data of each node.

        In the main block of code, the first input line reads in the number of nodes N, the starting index L, and the ending index R. The second input line reads in the values for each node. The linked list is constructed by inserting each node at the end using the insertEnd function. Finally, the reverseList function is called with the specified indices and the head of the linked list, and the resulting list is printed using the printList function.