n个节点的二叉树n+1

Given a linked list and an integer n, append the last n elements of the LL to front. Assume given n will be smaller than length of LL.

给定一个链表和一个整数n，将LL的最后n个元素附加到前面。 假设给定的n将小于LL的长度。

Input format: Line 1: Linked list elements (separated by space and terminated by -1

输入格式：第1行：链接的列表元素(以空格分隔并以-1终止

Sample Input 1 :    1 2 3 4 5 -1    3    Sample Output 1 :    3 4 5 1 2

Description:

描述：

The question asks us to append the last N nodes to front, i.e the new linked list should first start from those N nodes and then traverse the rest of the nodes through the head of the old linked list.

这个问题要求我们将最后的N个节点附加到前面，即新的链表应首先从这N个节点开始，然后再通过旧链表的头遍历其余节点。

Example:

例：

For Linked List 1->2->3->4->5->6->NULL    To append the last 2 nodes, the new linked list should be:    5->6->1->2->3->4->NULL

Solution Explanation:

解决方案说明：

To solve this problem, we take two pointers temp and t and point both of them to the head of the linked list. We take another variable i and equate it to – n. This i is used for finding out the head of the new linked list. Then we traverse the loop while temp != NULL. In the loop we check that if(i>=0) i.e temp is now n nodes away from t, t = t-> next. We will update i++ and temp = temp->next on each traversal. At last, we update temp-> next = head, head = t -> next and t-> next = NULL.

为了解决这个问题，我们使用两个指针temp和t并将它们都指向链接列表的开头。 我们采用另一个变量i并将其等于– n 。 我用于查找新链表的标题。 然后，我们在temp！= NULL时遍历循环。 在循环中，我们检查if(i> = 0)，即temp现在距离t距离n个节点， t = t-> next 。 我们将在每次遍历时更新i ++和temp = temp-> next 。 最后，我们更新temp-> next = head ， head = t-> next和t-> next = NULL 。

Algorithm:

算法：

• STEP 1: Declare the function appendNNode with parameters (Node* head, int n)

  步骤1：使用参数声明函数appendNNode (Node * head，int n)

• STEP 2: Declare two variables Node * temp , t and point both of them to head.

  步骤2：声明两个变量Node * temp ， t并将它们都指向head。

• STEP 3: Declare int i = -n

  步骤3：声明int i = -n

• STEP 4: Repeat Step 5 and 6, while(temp->next != NULL)

  步骤4：重复步骤5和6， 同时(temp-> next！= NULL)

• STEP 5: if(i>=0) t = t-> next.

  步骤5： if(i> = 0)t = t-> next 。

• STEP 6: temp = temp-> next, i++.

  步骤6： temp = temp->接下来，i ++ 。

• STEP 7: temp->next = head, head = t->next, and t-> next =NULL

  步骤7： temp-> next = head ， head = t-> next和t-> next = NULL

• STEP 8: return head

  步骤8：返回头

Steps:

脚步：

At first: 1->2->3->4->5->6->NULL, t->1 and temp->1.    After complete traversal: 1->2->3->4->5->6->NULL, t->4 and temp->6.    So, temp->next = head and head = t->next    i.e 5->6->1->2->3->4 --- (reconnecting to 5)    Atlast, t-> next = NULL    i.e 5->6->1->2->3->4->NULL

Function:

功能：

Node *appendNNodes(Node* head, int n){	// Two pointers, one for traversal and 	// other for finding the new head of LL	Node *temp = head, *t = head;           	//index maintained for finding new head	int i = -n;	while(temp->next!=NULL){		//When temp went forward n nodes from t		if(i>=0){                           			t = t->next;		}		temp = temp ->next;		i++;	}	//Connecting the tail to head	temp->next = head;                      	//Assigning the new node	head = t->next;                         	//Deleting the previous connection	t->next = NULL;                         	return head;}

C++ Code:

C ++代码：

#include
    
     using namespace std;struct Node{
   // linked list Node	int data;	Node * next;};Node *newNode(int k){
    //defining new node	Node *temp = (Node*)malloc(sizeof(Node)); 	temp->data = k; 	temp->next = NULL; 	return temp; }//Used to add new node at the end of the listNode *addNode(Node* head, int k){
   	if(head == NULL){
   		head = newNode(k);	}	else{
   		Node * temp = head;		Node * node = newNode(k);		while(temp->next!= NULL){
   			temp = temp->next;		}		temp-> next = node;	}	return head;}// Used to create new linked list and return headNode *createNewLL(){
   	int cont = 1;	int data;	Node* head = NULL;	while(cont){
   		cout<<"Enter the data of the Node"<
     
      >data;		head = addNode(head,data);		cout<<"Do you want to continue?(0/1)"<
      
       >cont;	}	return head;}//To print the Linked Listvoid *printLL(Node * head){
   	while(head!= NULL){
   		cout<
       
        data<<"->";		head = head-> next;	}	cout<<"NULL"<
        
         next!=NULL){
   		//When temp went forward n nodes from t		if(i>=0){
                             			t = t->next;		}		temp = temp ->next;		i++;	}	//Connecting the tail to head	temp->next = head;                      	//Assigning the new node	head = t->next;                         	//Deleting the previous connection	t->next = NULL;                         	return head;}//Driver Mainint main(){
   	Node * head = createNewLL();	cout<<"The linked list is"<
         
          >data; head = appendNNodes(head,data); cout<<"The new Linked List is" <
         
        
       
      
     
    

Output

输出量

Enter the data of the Node1Do you want to continue?(0/1)1Enter the data of the Node2Do you want to continue?(0/1)1Enter the data of the Node3Do you want to continue?(0/1)1Enter the data of the Node4Do you want to continue?(0/1)1Enter the data of the Node5Do you want to continue?(0/1)1Enter the data of the Node6Do you want to continue?(0/1)1Enter the data of the Node7Do you want to continue?(0/1)0The linked list is1->2->3->4->5->6->7->NULLEnter the number of nodes you want to append.3The new Linked List is5->6->7->1->2->3->4->NULL

翻译自:

n个节点的二叉树n+1