使用递归从中间顺序到左右顺序遍历链表

本文概述

  • C ++
  • Java
  • C#
【使用递归从中间顺序到左右顺序遍历链表】给定一个链表。任务是使用递归从中间顺序到左右顺序遍历链表。
例如:
如果给定的链表是:2-> 5-> 8-> 3-> 7-> 9-> 12-> NULL
中间从左到右的顺序是:3, 8, 7, 5, 5, 9, 2, 12
说明:给定链表的中间是'3', 所以我们从中间开始遍历, 先打印3, 然后在3的左边和右边, 所以我们打印8、7, 然后再打印8的左边, 然后在7的右边, 所以我们打印5、9, 然后在左边打印5, 在右边打印9, 因此我们打印2、12。
注意:如果链表中的节点数为偶数, 则仅从左向右打印。对于此链表(包含偶数个节点)2-> 5-> 8-> 7-> 9-> 12-> NULL。
输出应为8、7、5、9、2、12。
例子:
输入:20-> 15-> 23-> 13-> 19-> 32-> 16-> 41-> 11-> NULL
输出:19、13、32、23、16、15、41、20、11
输入:12-> 25-> 51-> 16-> 9-> 90-> 7-> 2-> NULL
输出:16, 9, 51, 90, 25, 7, 12, 2。
方法:
首先, 计算链表的大小:
  • 如果大小为奇数:
    -> 然后使用递归转到第(n + 1)/ 2个节点。
  • 如果大小是偶数:
    -> 然后使用递归转到第n / 2个节点。
  • 现在打印节点数据并返回下一个节点地址, 除非函数调用堆栈为空, 否则请执行此步骤。
下面是上述方法的实现:
C ++
//A C++ program to demonstrate //the printing of Linked List middle //to left right order#include < bits/stdc++.h> using namespace std; //A linked list node class Node { public : int data; Node* next; }; //Given a reference (pointer to pointer) //to the head of a list and an int, appends //a new node at the endvoid append(Node** head_ref, int new_data) { //Allocate node Node* new_node = new Node(); //Used in step 5 Node* last = *head_ref; //Put in the data new_node-> data = https://www.lsbin.com/new_data; //This new node is going to be //the last node, so make next of //it as NULL new_node-> next = NULL; //If the Linked List is empty, //then make the new node as head if (*head_ref == NULL) { *head_ref = new_node; return ; }//Else traverse till the last node while (last-> next != NULL) last = last-> next; //Change the next of last node last-> next = new_node; return ; }//This function prints contents of //linked list starting from headvoid printList(Node* node) { while (node != NULL) { cout < <" " < < node-> data; if (node-> next != NULL) cout < < "-> " ; node = node-> next; } }//Function to get the size of linked list int getSize(Node* head) { if (head == NULL) return 0; return 1 + getSize(head-> next); }//Utility function to print the Linked List //from middle to left right order Node* printMiddleToLeftRightUtil(Node* head, int counter, int lSize) { //Base Condition //When size of list is odd if (counter == 1 & & lSize % 2 != 0) {//Print node value cout < < head-> data; //Returns address of next node return head-> next; }//Base Condition //When size of list is even else if (counter == 1) {//Print node value //and next node value cout < < head-> data; cout < < " , " < < head-> next-> data; //Returns address of next to next node return head-> next-> next; } else {//Recursive function call and //store return address Node* ptr = printMiddleToLeftRightUtil( head-> next, counter - 1, lSize); //Print head data cout < < " , " < < head-> data; //Print ptr data cout < < " , " < < ptr-> data; //Returns address of next node return ptr-> next; } }//Function to print Middle to //Left-right order void printMiddleToLeftRight(Node* head) { //Function call to get the size //Of Linked List int listSize = getSize(head); int middle = 0; //Store middle when Linked //List size is odd if (listSize % 2 != 0) { middle = (listSize + 1) /2; }//Store middle when Linked //List size is evenelse { middle = listSize /2; }//Utility function call print //Linked List from Middle //to left right order cout < < "Output : " ; printMiddleToLeftRightUtil(head, middle, listSize); }//Driver code int main() { //Start with the empty list Node* head = NULL; //Insert 6. So linked list //becomes 6-> NULL append(& head, 6); //Insert 6. So linked list //becomes 6-> 4-> NULL append(& head, 4); append(& head, 8); append(& head, 7); append(& head, 9); append(& head, 11); append(& head, 2); //After inserting linked list //becomes 6-> 4-> 8-> 7-> 9-> 11-> 2-> NULL cout < < "Created Linked list is: " ; //Function to display Linked List content printList(head); cout < < endl; //Function call print Linked List from //Middle to left right order printMiddleToLeftRight(head); return 0; }

Java
//A Java program to demonstrate //the printing of Linked List middle //to left right order class GFG {//A linked list node static class Node { int data; Node next; }; //Given a reference (pointer to pointer) //to the head of a list and an int, appends //a new node at the end static Node append(Node head_ref, int new_data) { //Allocate node Node new_node = new Node(); //Used in step 5 Node last = head_ref; //Put in the data new_node.data = https://www.lsbin.com/new_data; //This new node is going to be //the last node, so make next of //it as null new_node.next = null ; //If the Linked List is empty, //then make the new node as head if (head_ref == null ) { head_ref = new_node; return head_ref; }//Else traverse till the last node while (last.next != null ) last = last.next; //Change the next of last node last.next = new_node; return head_ref; }//This function prints contents of //linked list starting from head static void printList(Node node) { while (node != null ) { System.out.print(" " + node.data); if (node.next != null ) System.out.print( "-> " ); node = node.next; } }//Function to get the size of linked list static int getSize(Node head) { if (head == null ) return 0 ; return 1 + getSize(head.next); }//Utility function to print the Linked List //from middle to left right order static Node printMiddleToLeftRightUtil(Node head, int counter, int lSize) { //Base Condition //When size of list is odd if (counter == 1 & & lSize % 2 != 0 ) {//Print node value System.out.print( head.data); //Returns address of next node return head.next; }//Base Condition //When size of list is even else if (counter == 1 ) {//Print node value //and next node value System.out.print(head.data); System.out.print( " , " + head.next.data); //Returns address of next to next node return head.next.next; } else {//Recursive function call and //store return address Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1 , lSize); //Print head data System.out.print( " , " + head.data); //Print ptr data System.out.print( " , " + ptr.data); //Returns address of next node return ptr.next; } }//Function to print Middle to //Left-right order static void printMiddleToLeftRight(Node head) { //Function call to get the size //Of Linked List int listSize = getSize(head); int middle = 0 ; //Store middle when Linked //List size is odd if (listSize % 2 != 0 ) { middle = (listSize + 1 ) /2 ; }//Store middle when Linked //List size is even else { middle = listSize /2 ; }//Utility function call print //Linked List from Middle //to left right order System.out.print( "Output : " ); printMiddleToLeftRightUtil(head, middle, listSize); }//Driver code public static void main(String args[]) { //Start with the empty list Node head = null ; //Insert 6. So linked list //becomes 6.null head = append(head, 6 ); //Insert 6. So linked list //becomes 6.4.null head = append(head, 4 ); head = append(head, 8 ); head = append(head, 7 ); head = append(head, 9 ); head = append(head, 11 ); head = append(head, 2 ); //After inserting linked list //becomes 6.4.8.7.9.11.2.null System.out.print( "Created Linked list is: " ); //Function to display Linked List content printList(head); System.out.println(); //Function call print Linked List from //Middle to left right order printMiddleToLeftRight(head); } }//This code is contributed by Arnab Kundu

C#
//A C# program to demonstrate //the printing of Linked List middle //to left right order using System; public class GFG {//A linked list node public class Node { public int data; public Node next; }; //Given a reference (pointer to pointer) //to the head of a list and an int, appends //a new node at the end static Node append(Node head_ref, int new_data) { //Allocate node Node new_node = new Node(); //Used in step 5 Node last = head_ref; //Put in the data new_node.data = https://www.lsbin.com/new_data; //This new node is going to be //the last node, so make next of //it as null new_node.next = null ; //If the Linked List is empty, //then make the new node as head if (head_ref == null ) { head_ref = new_node; return head_ref; }//Else traverse till the last node while (last.next != null ) last = last.next; //Change the next of last node last.next = new_node; return head_ref; }//This function prints contents of //linked list starting from head static void printList(Node node) { while (node != null ) { Console.Write(" " + node.data); if (node.next != null ) Console.Write( "-> " ); node = node.next; } }//Function to get the size of linked list static int getSize(Node head) { if (head == null ) return 0; return 1 + getSize(head.next); }//Utility function to print the Linked List //from middle to left right order static Node printMiddleToLeftRightUtil(Node head, int counter, int lSize) { //Base Condition //When size of list is odd if (counter == 1 & & lSize % 2 != 0) {//Print node value Console.Write( head.data); //Returns address of next node return head.next; }//Base Condition //When size of list is even else if (counter == 1) {//Print node value //and next node value Console.Write(head.data); Console.Write( " , " + head.next.data); //Returns address of next to next node return head.next.next; } else {//Recursive function call and //store return address Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1, lSize); //Print head data Console.Write( " , " + head.data); //Print ptr data Console.Write( " , " + ptr.data); //Returns address of next node return ptr.next; } }//Function to print Middle to //Left-right order static void printMiddleToLeftRight(Node head) { //Function call to get the size //Of Linked List int listSize = getSize(head); int middle = 0; //Store middle when Linked //List size is odd if (listSize % 2 != 0) { middle = (listSize + 1) /2; }//Store middle when Linked //List size is even else { middle = listSize /2; }//Utility function call print //Linked List from Middle //to left right order Console.Write( "Output : " ); printMiddleToLeftRightUtil(head, middle, listSize); }//Driver code public static void Main(String []args) { //Start with the empty list Node head = null ; //Insert 6. So linked list //becomes 6.null head = append(head, 6); //Insert 6. So linked list //becomes 6.4.null head = append(head, 4); head = append(head, 8); head = append(head, 7); head = append(head, 9); head = append(head, 11); head = append(head, 2); //After inserting linked list //becomes 6.4.8.7.9.11.2.null Console.Write( "Created Linked list is: " ); //Function to display Linked List content printList(head); Console.WriteLine(); //Function call print Linked List from //Middle to left right order printMiddleToLeftRight(head); } }//This code is contributed by Rajput-Ji

输出如下:
Created Linked list is:6-> 4-> 8-> 7-> 9-> 11-> 2 Output : 7 , 8 , 9 , 4 , 11 , 6 , 2

    推荐阅读