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

2021年4月25日17:08:54 发表评论 635 次浏览

## 本文概述

• 如果大小为奇数：
->然后使用递归转到第(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;

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 end

{
//Allocate node
Node* new_node = new Node();

//Used in step 5

//Put in the data
new_node->data = 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
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

void 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
{
return 0;
}

//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

}

//Base Condition
//When size of list is even
else if (counter == 1) {

//Print node value
//and next node value

//Returns address of next to next node
}
else {

//Recursive function call and
Node* ptr = printMiddleToLeftRightUtil(

//Print ptr data
cout <<" , " <<ptr->data;

return ptr->next;
}
}

//Function to print Middle to
//Left-right order
{
//Function call to get the size

int middle = 0;

//List size is odd
if (listSize % 2 != 0) {
middle = (listSize + 1) /2;
}

//List size is even

else {
middle = listSize /2;
}

//Utility function call print
//to left right order
cout <<"Output : " ;

}

//Driver code
int main()
{

//becomes 6->NULL

//becomes 6->4->NULL

//becomes 6->4->8->7->9->11->2->NULL
cout <<"Created Linked list is: " ;

//Function to display Linked List content
cout <<endl;

//Function call print Linked List from
//Middle to left right order
return 0;
}``````

## Java

``````//A Java program to demonstrate
//the printing of Linked List middle
//to left right order
class GFG
{

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

//Put in the data
new_node.data = 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
{
}

//Else traverse till the last node
while (last.next != null )
last = last.next;

//Change the next of last node
last.next = new_node;
}

//This function prints contents of
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
{
return 0 ;
}

//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

}

//Base Condition
//When size of list is even
else if (counter == 1 )
{

//Print node value
//and next node value
System.out.print( " , " + head.next.data);

//Returns address of next to next node
}
else
{

//Recursive function call and
Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1 , lSize);

System.out.print( " , " + head.data);

//Print ptr data
System.out.print( " , " + ptr.data);

return ptr.next;
}
}

//Function to print Middle to
//Left-right order
{
//Function call to get the size

int middle = 0 ;

//List size is odd
if (listSize % 2 != 0 )
{
middle = (listSize + 1 ) /2 ;
}

//List size is even
else
{
middle = listSize /2 ;
}

//Utility function call print
//to left right order
System.out.print( "Output : " );

}

//Driver code
public static void main(String args[])
{

//becomes 6.null

//becomes 6.4.null

//becomes 6.4.8.7.9.11.2.null
System.out.print( "Created Linked list is: " );

//Function to display Linked List content
System.out.println();

//Function call print Linked List from
//Middle to left right order
}
}

//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
{

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

//Put in the data
new_node.data = 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
{
}

//Else traverse till the last node
while (last.next != null )
last = last.next;

//Change the next of last node
last.next = new_node;
}

//This function prints contents of
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
{
return 0;
}

//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

}

//Base Condition
//When size of list is even
else if (counter == 1)
{

//Print node value
//and next node value
Console.Write( " , " + head.next.data);

//Returns address of next to next node
}
else
{

//Recursive function call and
Node ptr = printMiddleToLeftRightUtil(head.next, counter - 1, lSize);

Console.Write( " , " + head.data);

//Print ptr data
Console.Write( " , " + ptr.data);

return ptr.next;
}
}

//Function to print Middle to
//Left-right order
{
//Function call to get the size

int middle = 0;

//List size is odd
if (listSize % 2 != 0)
{
middle = (listSize + 1) /2;
}

//List size is even
else
{
middle = listSize /2;
}

//Utility function call print
//to left right order
Console.Write( "Output : " );

}

//Driver code
public static void Main(String []args)
{

//becomes 6.null

//becomes 6.4.null

//becomes 6.4.8.7.9.11.2.null
Console.Write( "Created Linked list is: " );

//Function to display Linked List content
Console.WriteLine();

//Function call print Linked List from
//Middle to left right order
``````Created Linked list is:  6-> 4-> 8-> 7-> 9-> 11-> 2