鉴于 循环链表 交换第一个和最后一个节点。该任务应该只使用一个额外的节点来完成，不能声明多个额外的节点，也不允许声明任何其他临时变量。 注： 额外节点意味着节点需要遍历列表。
null
例如：
Input : 5 4 3 2 1Output : 1 4 3 2 5Input : 6 1 2 3 4 5 6 7 8 9Output : 9 1 2 3 4 5 6 7 8 6
方法1： （通过更改第一个和最后一个节点的链接） 我们首先找到指向最后一个节点前一个节点的指针。让这个节点为p。现在我们更改下一个链接，以便交换最后一个和第一个节点。
C++
// CPP program to exchange first and // last node in circular linked list #include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; struct Node* addToEmpty( struct Node* head, int data) { // This function is only for empty list if (head != NULL) return head; // Creating a node dynamically. struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); // Assigning the data. temp->data = data; head = temp; // Creating the link. head->next = head; return head; } struct Node* addBegin( struct Node* head, int data) { if (head == NULL) return addToEmpty(head, data); struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); temp->data = data; temp->next = head->next; head->next = temp; return head; } /* function for traversing the list */ void traverse( struct Node* head) { struct Node* p; // If list is empty, return. if (head == NULL) { cout << "List is empty." << endl; return ; } // Pointing to first Node of the list. p = head; // Traversing the list. do { cout << p->data << " " ; p = p->next; } while (p != head); } /* Function to exchange first and last node*/ struct Node* exchangeNodes( struct Node* head) { // If list is of length 2 if (head->next->next == head) { head = head->next; return head; } // Find pointer to previous of last node struct Node* p = head; while (p->next->next != head) p = p->next; /* Exchange first and last nodes using head and p */ p->next->next = head->next; head->next = p->next; p->next = head; head = head->next; return head; } // Driven Program int main() { int i; struct Node* head = NULL; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); cout << "List Before: " ; traverse(head); cout << endl; cout << "List After: " ; head = exchangeNodes(head); traverse(head); return 0; } |
JAVA
// Java program to exchange // first and last node in // circular linked list class GFG { static class Node { int data; Node next; }; static Node addToEmpty(Node head, int data) { // This function is only // for empty list if (head != null ) return head; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } static Node addBegin(Node head, int data) { if (head == null ) return addToEmpty(head, data); Node temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } // function for traversing the list static void traverse(Node head) { Node p; // If list is empty, return. if (head == null ) { System.out.print( "List is empty." ); return ; } // Pointing to first // Node of the list. p = head; // Traversing the list. do { System.out.print(p.data + " " ); p = p.next; } while (p != head); } // Function to exchange // first and last node static Node exchangeNodes(Node head) { // If list is of length 2 if (head.next.next == head) { head = head.next; return head; } // Find pointer to previous // of last node Node p = head; while (p.next.next != head) p = p.next; // Exchange first and last // nodes using head and p p.next.next = head.next; head.next = p.next; p.next = head; head = head.next; return head; } // Driver Code public static void main(String args[]) { int i; Node head = null ; head = addToEmpty(head, 6 ); for (i = 5 ; i > 0 ; i--) head = addBegin(head, i); System.out.print( "List Before: " ); traverse(head); System.out.println(); System.out.print( "List After: " ); head = exchangeNodes(head); traverse(head); } } // This code is contributed // by Arnab Kundu |
Python3
# Python3 program to exchange first and # last node in circular linked list import math class Node: def __init__( self , data): self .data = data self . next = None def addToEmpty(head, data): # This function is only for empty list if (head ! = None ): return head # Creating a node dynamically. temp = Node(data) # Assigning the data. temp.data = data head = temp # Creating the link. head. next = head return head def addBegin(head, data): if (head = = None ): return addToEmpty(head, data) temp = Node(data) temp.data = data temp. next = head. next head. next = temp return head # function for traversing the list def traverse(head): # If list is empty, return. if (head = = None ): print ( "List is empty." ) return # Pointing to first Node of the list. p = head print (p.data, end = " " ) p = p. next # Traversing the list. while (p ! = head): print (p.data, end = " " ) p = p. next def exchangeNodes(head): # Cases Handled: Linked List either empty or containing single node. if head = = None or head. next = = head: return head # Cases Handled: Linked List containing only two nodes elif head. next . next = = head: head = head. next return head # Cases Handled: Linked List containing multiple nodes else : prev = None curr = head temp = head # finding last and second last nodes in linkedlist list while curr. next ! = head: prev = curr curr = curr. next # point the last node to second node of the list curr. next = temp. next # point the second last node to first node prev. next = temp # point the end of node to start ( make linked list circular ) temp. next = curr # mark the starting of linked list head = curr return head # Driver Code if __name__ = = '__main__' : head = None head = addToEmpty(head, 6 ) for x in range ( 5 , 0 , - 1 ): head = addBegin(head, x) print ( "List Before: " , end = "") traverse(head) print () print ( "List After: " , end = "") head = exchangeNodes(head) traverse(head) # This code is contributed by Srathore # Improved by Vinay Kumar (vinaykumar71) |
C#
// C# program to exchange // first and last node in // circular linked list using System; public class GFG { class Node { public int data; public Node next; }; static Node addToEmpty(Node head, int data) { // This function is only // for empty list if (head != null ) return head; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } static Node addBegin(Node head, int data) { if (head == null ) return addToEmpty(head, data); Node temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } // function for traversing the list static void traverse(Node head) { Node p; // If list is empty, return. if (head == null ) { Console.Write( "List is empty." ); return ; } // Pointing to first // Node of the list. p = head; // Traversing the list. do { Console.Write(p.data + " " ); p = p.next; } while (p != head); } // Function to exchange // first and last node static Node exchangeNodes(Node head) { // If list is of length 2 if (head.next.next == head) { head = head.next; return head; } // Find pointer to previous // of last node Node p = head; while (p.next.next != head) p = p.next; // Exchange first and last // nodes using head and p p.next.next = head.next; head.next = p.next; p.next = head; head = head.next; return head; } // Driver Code public static void Main() { int i; Node head = null ; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); Console.Write( "List Before: " ); traverse(head); Console.WriteLine(); Console.Write( "List After: " ); head = exchangeNodes(head); traverse(head); } } /* This code is contributed PrinciRaj1992 */ |
Javascript
<script> // javascript program to exchange // first and last node in // circular linked list class Node { constructor() { this .data = 0; this .next = null ; } } function addToEmpty(head , data) { // This function is only // for empty list if (head != null ) return head; // Creating a node dynamically. var temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } function addBegin(head , data) { if (head == null ) return addToEmpty(head, data); var temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } // function for traversing the list function traverse(head) { var p; // If list is empty, return. if (head == null ) { document.write( "List is empty." ); return ; } // Pointing to first // Node of the list. p = head; // Traversing the list. do { document.write(p.data + " " ); p = p.next; } while (p != head); } // Function to exchange // first and last node function exchangeNodes(head) { // If list is of length 2 if (head.next.next == head) { head = head.next; return head; } // Find pointer to previous // of last node var p = head; while (p.next.next != head) p = p.next; // Exchange first and last // nodes using head and p p.next.next = head.next; head.next = p.next; p.next = head; head = head.next; return head; } // Driver Code var i; var head = null ; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); document.write( "List Before: " ); traverse(head); document.write( "<br/>" ); document.write( "List After: " ); head = exchangeNodes(head); traverse(head); // This code is contributed by umadevi9616 </script> |
输出
List Before: 6 1 2 3 4 5 List After: 5 1 2 3 4 6
方法2： （通过交换第一个和最后一个节点的值）
算法：
- 遍历列表并找到最后一个节点（尾部）。
- 交换头部和尾部的数据。
以下是算法的实现：
C++
// CPP program to exchange first and // last node in circular linked list #include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; struct Node* addToEmpty( struct Node* head, int data) { // This function is only for empty list if (head != NULL) return head; // Creating a node dynamically. struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); // Assigning the data. temp->data = data; head = temp; // Creating the link. head->next = head; return head; } struct Node* addBegin( struct Node* head, int data) { if (head == NULL) return addToEmpty(head, data); struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node)); temp->data = data; temp->next = head->next; head->next = temp; return head; } /* function for traversing the list */ void traverse( struct Node* head) { struct Node* p; // If list is empty, return. if (head == NULL) { cout << "List is empty." << endl; return ; } // Pointing to first Node of the list. p = head; // Traversing the list. do { cout << p->data << " " ; p = p->next; } while (p != head); } /* Function to exchange first and last node*/ struct Node* exchangeNodes( struct Node* head) { // If list is of length less than 2 if (head == NULL || head->next == NULL) { return head; } Node* tail = head; // Find pointer to the last node while (tail->next != head) { tail = tail->next; } /* Exchange first and last nodes using head and p */ // temporary variable to store // head data int temp = tail->data; tail->data = head->data; head->data = temp; return head; } // Driven Program int main() { int i; struct Node* head = NULL; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); cout << "List Before: " ; traverse(head); cout << endl; cout << "List After: " ; head = exchangeNodes(head); traverse(head); return 0; } |
JAVA
// JAVA program to exchange first and // last node in circular linked list class GFG{ static class Node { int data; Node next; }; static Node addToEmpty(Node head, int data) { // This function is only for empty list if (head != null ) return head; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } static Node addBegin(Node head, int data) { if (head == null ) return addToEmpty(head, data); Node temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } /* function for traversing the list */ static void traverse(Node head) { Node p; // If list is empty, return. if (head == null ) { System.out.print( "List is empty." + "" ); return ; } // Pointing to first Node of the list. p = head; // Traversing the list. do { System.out.print(p.data+ " " ); p = p.next; } while (p != head); } /* Function to exchange first and last node*/ static Node exchangeNodes(Node head) { // If list is of length less than 2 if (head == null || head.next == null ) { return head; } Node tail = head; // Find pointer to the last node while (tail.next != head) { tail = tail.next; } /* Exchange first and last nodes using head and p */ // temporary variable to store // head data int temp = tail.data; tail.data = head.data; head.data = temp; return head; } // Driven Program public static void main(String[] args) { int i; Node head = null ; head = addToEmpty(head, 6 ); for (i = 5 ; i > 0 ; i--) head = addBegin(head, i); System.out.print( "List Before: " ); traverse(head); System.out.println(); System.out.print( "List After: " ); head = exchangeNodes(head); traverse(head); } } // This code is contributed by umadevi9616 |
C#
// C# program to exchange first and // last node in circular linked list using System; public class GFG { public class Node { public int data; public Node next; }; static Node addToEmpty(Node head, int data) { // This function is only for empty list if (head != null ) return head; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } static Node addBegin(Node head, int data) { if (head == null ) return addToEmpty(head, data); Node temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } /* function for traversing the list */ static void traverse(Node head) { Node p; // If list is empty, return. if (head == null ) { Console.Write( "List is empty." + "" ); return ; } // Pointing to first Node of the list. p = head; // Traversing the list. do { Console.Write(p.data + " " ); p = p.next; } while (p != head); } /* Function to exchange first and last node */ static Node exchangeNodes(Node head) { // If list is of length less than 2 if (head == null || head.next == null ) { return head; } Node tail = head; // Find pointer to the last node while (tail.next != head) { tail = tail.next; } /* * Exchange first and last nodes using head and p */ // temporary variable to store // head data int temp = tail.data; tail.data = head.data; head.data = temp; return head; } // Driven Program public static void Main(String[] args) { int i; Node head = null ; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); Console.Write( "List Before: " ); traverse(head); Console.WriteLine(); Console.Write( "List After: " ); head = exchangeNodes(head); traverse(head); } } // This code is contributed by umadevi9616 |
Javascript
<script> // javascript program to exchange first and // last node in circular linked list class Node { class Node { constructor() { this .data = 0; this .next = null ; } } function addToEmpty(head , data) { // This function is only for empty list if (head != null ) return head; // Creating a node dynamically. var temp = new Node(); // Assigning the data. temp.data = data; head = temp; // Creating the link. head.next = head; return head; } function addBegin(head , data) { if (head == null ) return addToEmpty(head, data); var temp = new Node(); temp.data = data; temp.next = head.next; head.next = temp; return head; } /* function for traversing the list */ function traverse(head) { var p; // If list is empty, return. if (head == null ) { document.write( "List is empty." + "" ); return ; } // Pointing to first Node of the list. p = head; // Traversing the list. do { document.write(p.data + " " ); p = p.next; } while (p != head); } /* Function to exchange first and last node */ function exchangeNodes(head) { // If list is of length less than 2 if (head == null || head.next == null ) { return head; } var tail = head; // Find pointer to the last node while (tail.next != head) { tail = tail.next; } /* * Exchange first and last nodes using head and p */ // temporary variable to store // head data var temp = tail.data; tail.data = head.data; head.data = temp; return head; } // Driven Program var i; var head = null ; head = addToEmpty(head, 6); for (i = 5; i > 0; i--) head = addBegin(head, i); document.write( "List Before: <br/>" ); traverse(head); document.write( "<br/>" ); document.write( "List After: <br/>" ); head = exchangeNodes(head); traverse(head); // This code is contributed by umadevi9616 </script> |
输出
List Before: 6 1 2 3 4 5 List After: 5 1 2 3 4 6
时间复杂性： 
本文由 拉杰 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
