给定一个链表，在0之前有两个相邻的重复节点，任务是将第一个节点加倍，然后使下一个节点为0。在此之后，将所有的零附加到尾部。 先决条件： 单链表实现的基础
null
例如：
Input : 4 -> 4 -> 0 -> 2 -> 3 -> 4 -> 3 -> 3 -> 0 -> 4 -> Output : 8-> 2-> 3-> 4-> 6-> 4-> 0-> 0-> 0-> 0-> Explanation :First, after doubling the first element and makingsecond element 0 before all zeros.8 -> 0 -> 0 -> 2 -> 3 -> 4 -> 6 -> 0 -> 0 -> 4 ->Next :8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> Input : 0 -> 4 -> 4 -> 0 -> 3 -> 3 -> 0 -> 5 -> 0 -> 0 -> 6 ->Output : 8 -> 6 -> 5 -> 6 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 -> 0 ->
遍历链表，如果在0之前有两个相邻的相同节点数据（例如4->4->0），则将第一个元素加倍，并将另一个元素设为0（例如8->0->）。最后，遍历链表，线性地将所有的零指向尾部。
JAVA
// Java code to modify linked list import java.util.*; // Linked List Node class Node { int data; Node next; // Constructor public Node( int data) { this .data = data; next = null ; } } // Class ro perform operations // on linked list class GfG { // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 public static void changeTwoBefore0(Node head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null ) return ; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0 )) { int temp = head.data; head.data = 2 * temp; head.next.data = 0 ; if (head.next.next.next != null ) head = head.next.next.next; else return ; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail public static Node appendZero(Node head) { if (head == null || head.next == null ) return head; // Find tail node Node tail = head; while (tail.next != null ) tail = tail.next; Node origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node curr = head; while (curr.next != null && curr.data == 0 ) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end Node prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0 ) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null ; return head; } public static Node doubleAndAppend0(Node head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes public static void display(Node head) { while (head != null ) { System.out.print(head.data + " -> " ); head = head.next; } } // Driver code public static void main(String[] args) { Node head = new Node( 4 ); head.next = new Node( 4 ); head.next.next = new Node( 0 ); head.next.next.next = new Node( 2 ); head.next.next.next.next = new Node( 3 ); head.next.next.next.next.next = new Node( 4 ); head.next.next.next.next.next.next = new Node( 3 ); head.next.next.next.next.next.next.next = new Node( 3 ); head.next.next.next.next.next.next.next.next = new Node( 0 ); head.next.next.next.next.next.next.next.next.next = new Node( 4 ); System.out.println( "Original linked list :" ); display(head); head = doubleAndAppend0(head); System.out.println( "Modified linked list :" ); display(head); } } |
C++
// C++ code to modify linked list #include <bits/stdc++.h> using namespace std; // Linked List Node class Node { public : int data; Node* next; // Constructor public : Node( int dat) { data = dat; next = NULL; } }; // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 void changeTwoBefore0(Node* head) { // there should be atleast three elements // to perform required operation if (head == NULL || head->next == NULL || head->next->next == NULL) return ; // when two continuous elements // are same if ((head->data == head->next->data) && (head->next->next->data == 0)) { int temp = head->data; head->data = 2 * temp; head->next->data = 0; if (head->next->next->next != NULL) head = head->next->next->next; else return ; } else head = head->next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail Node* appendZero(Node* head) { if (head == NULL || head->next == NULL) return head; // Find tail node Node* tail = head; while (tail->next != NULL) tail = tail->next; Node* origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node* curr = head; while (curr->next != NULL && curr->data == 0) { tail->next = curr; tail = curr; curr = curr->next; } head = curr; // Now moving other 0s to end Node* prev = curr; curr = curr->next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr->data == 0) { tail->next = curr; tail = curr; prev->next = curr->next; } else prev = curr; // We always move current curr = curr->next; } // Finally making sure that linked // list is NULL terminated. tail->next = NULL; return head; } Node* doubleAndAppend0(Node* head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes void display(Node* head) { while (head != NULL) { cout << head->data << " -> " ; head = head->next; } } // Driver Code int main() { Node* head = new Node(4); head->next = new Node(4); head->next->next = new Node(0); head->next->next->next = new Node(2); head->next->next->next->next = new Node(3); head->next->next->next->next->next = new Node(4); head->next->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next->next->next = new Node(0); head->next->next->next->next->next->next->next->next ->next = new Node(4); cout << "Original linked list :" ; display(head); head = doubleAndAppend0(head); cout << "Modified linked list :" ; display(head); return 0; } // contributed by ajaykr00kj |
Python3
# Python3 code to modify linked list # Linked List Node class Node: # Constructor def __init__( self , data): self .data = data self . next = None # Recursive function to double the one of two # elements and make next one as 0, # which are equal before 0 def changeTwoBefore0 (head): # there should be atleast three elements # to perform required operation if (head = = None or head. next = = None or head. next . next = = None ): return # when two continuous elements # are same if ((head.data = = head. next .data) and (head. next . next .data = = 0 )): temp = head.data head.data = 2 * temp head. next .data = 0 if (head. next . next . next ! = None ): head = head. next . next . next else : return else : head = head. next # recursive call to changeTwoBefore0 # for next element changeTwoBefore0(head) # function to append zeros at tail def appendZero( head): if (head = = None or head. next = = None ): return head # Find tail node tail = head while (tail. next ! = None ): tail = tail. next origTail = tail # Case when starting nodes have 0 values # we need to change head in this case. curr = head while (curr. next ! = None and curr.data = = 0 ): tail. next = curr tail = curr curr = curr. next head = curr # Now moving other 0s to end prev = curr curr = curr. next # We check until original tail while (curr ! = origTail): # If current data is 0, append # after tail and update tail. if (curr.data = = 0 ): tail. next = curr tail = curr prev. next = curr. next else : prev = curr # We always move current curr = curr. next # Finally making sure that linked # list is None terminated. tail. next = None return head def doubleAndAppend0(head): # Change two same nodes before 0 changeTwoBefore0(head) # Move all 0s to end return appendZero(head) # function to display the nodes def display( head): while (head ! = None ): print (head.data ,end = " -> " ) head = head. next # Driver code head = Node( 4 ) head. next = Node( 4 ) head. next . next = Node( 0 ) head. next . next . next = Node( 2 ) head. next . next . next . next = Node( 3 ) head. next . next . next . next . next = Node( 4 ) head. next . next . next . next . next . next = Node( 3 ) head. next . next . next . next . next . next . next = Node( 3 ) head. next . next . next . next . next . next . next . next = Node( 0 ) head. next . next . next . next . next . next . next . next . next = Node( 4 ) print ( "Original linked list :" ) display(head) head = doubleAndAppend0(head) print ( "Modified linked list :" ) display(head) # This code is contributed by Arnab Kundu |
C#
// C# code to modify linked list using System; // Linked List Node public class Node { public int data; public Node next; // Constructor public Node( int data) { this .data = data; next = null ; } } // Class ro perform operations // on linked list public class GfG { // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 public static void changeTwoBefore0(Node head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null ) return ; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0)) { int temp = head.data; head.data = 2*temp; head.next.data = 0; if (head.next.next.next != null ) head = head.next.next.next; else return ; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail public static Node appendZero(Node head) { if (head == null || head.next == null ) return head; // Find tail node Node tail = head; while (tail.next != null ) tail = tail.next; Node origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. Node curr = head; while (curr.next != null && curr.data == 0) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end Node prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null ; return head; } public static Node doubleAndAppend0(Node head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes public static void display(Node head) { while (head != null ) { Console.Write(head.data + " -> " ); head = head.next; } } // Driver code public static void Main() { Node head = new Node(4); head.next = new Node(4); head.next.next = new Node(0); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next.next.next.next = new Node(4); Console.Write( "Original linked list :" ); display(head); head = doubleAndAppend0(head); Console.WriteLine( "Modified linked list :" ); display(head); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript code to modify linked list // Linked List Node class Node { constructor(data) { this .data = data; this .next = null ; } } // Class ro perform operations // on linked list // Recursive function to double the one of two // elements and make next one as 0, // which are equal before 0 function changeTwoBefore0(head) { // there should be atleast three elements // to perform required operation if (head == null || head.next == null || head.next.next == null ) return ; // when two continuous elements // are same if ((head.data == head.next.data) && (head.next.next.data == 0)) { var temp = head.data; head.data = 2*temp; head.next.data = 0; if (head.next.next.next != null ) head = head.next.next.next; else return ; } else head = head.next; // recursive call to changeTwoBefore0 // for next element changeTwoBefore0(head); } // function to append zeros at tail function appendZero(head) { if (head == null || head.next == null ) return head; // Find tail node var tail = head; while (tail.next != null ) tail = tail.next; var origTail = tail; // Case when starting nodes have 0 values // we need to change head in this case. var curr = head; while (curr.next != null && curr.data == 0) { tail.next = curr; tail = curr; curr = curr.next; } head = curr; // Now moving other 0s to end var prev = curr; curr = curr.next; // We check until original tail while (curr != origTail) { // If current data is 0, append // after tail and update tail. if (curr.data == 0) { tail.next = curr; tail = curr; prev.next = curr.next; } else prev = curr; // We always move current curr = curr.next; } // Finally making sure that linked // list is null terminated. tail.next = null ; return head; } function doubleAndAppend0(head) { // Change two same nodes before 0 changeTwoBefore0(head); // Move all 0s to end return appendZero(head); } // function to display the nodes function display( head) { while (head != null ) { document.write(head.data + " -> " ); head = head.next; } } // Driver code var head = new Node(4); head.next = new Node(4); head.next.next = new Node(0); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next.next.next.next = new Node(4); document.write( "Original linked list :<br>" ); display(head); head = doubleAndAppend0(head); document.write( "<br>Modified linked list :<br>" ); display(head); </script> |
输出
Original linked list :4 -> 4 -> 0 -> 2 -> 3 -> 4 -> 3 -> 3 -> 0 -> 4 -> Modified linked list :8 -> 2 -> 3 -> 4 -> 6 -> 4 -> 0 -> 0 -> 0 -> 0 ->
时间复杂性： O（n），其中n是链表的节点数。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
