本文概述

• C ++
• Java
• python
• C#
• C ++
• Java
• C#

给定一个包含以下内容的单链表
n个节点。修改前半节点的值, 以使第一个节点的新值等于最后一个节点的值减去第一个节点的当前值, 第二个节点的新值等于后一个节点的值减去第二个节点的当前值, 对于前半节点也是如此。如果n如果为奇数, 则中间节点的值保持不变。
(没有多余的内存可以使用)。
例子：

Input : 10 -> 4 -> 5 -> 3 -> 6 Output : 4 -> 1 -> 5 -> 3 -> 6Input : 2 -> 9 -> 8 -> 12 -> 7 -> 10 Output : -8 -> 2 -> -4 -> 12 -> 7 -> 10

在亚马逊采访中问
方法：以下步骤是：

1. 从中间拆分列表。执行前后拆分。如果元素的数量为奇数, 则多余的元素应放在第一(前)列表中。
2. 反转第二个(后退)列表.
3. 同时遍历两个列表时, 请执行所需的减法操作。
4. 再次反转第二个列表。
5. 将第二个列表连接回第一个列表的末尾。

C ++

//C++ implementation to modify the contents of //the linked list #include < bits/stdc++.h> using namespace std; /* Linked list node */ struct Node { int data; struct Node* next; }; /* function prototype for printing the list */ void printList( struct Node*); /* Function to insert a node at the beginning of the linked list */ void push( struct Node **head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data*/ new_node-> data = https://www.lsbin.com/new_data; /* link the old list at the end of the new node */ new_node-> next = *head_ref; /* move the head to point to the new node */ *head_ref = new_node; } /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. Uses the fast/slow pointer strategy. */ void frontAndBackSplit( struct Node *head, struct Node **front_ref, struct Node **back_ref) { Node *slow, *fast; slow = head; fast = head-> next; /* Advance'fast' two nodes, and advance 'slow' one node */ while (fast != NULL) { fast = fast-> next; if (fast != NULL) { slow = slow-> next; fast = fast-> next; } }/* 'slow' is before the midpoint in the list, so split it in two at that point. */ *front_ref = head; *back_ref = slow-> next; slow-> next = NULL; }/* Function to reverse the linked list */ void reverseList( struct Node **head_ref) { struct Node *current, *prev, *next; current = *head_ref; prev = NULL; while (current != NULL) { next = current-> next; current-> next = prev; prev = current; current = next; } *head_ref = prev; }//perfrom the required subtraction operation on //the 1st half of the linked list void modifyTheContentsOf1stHalf( struct Node *front, struct Node *back) { //traversing both the lists simultaneously while (back != NULL) { //subtraction operation and node data //modification front-> data = https://www.lsbin.com/front-> data - back-> data; front = front-> next; back = back-> next; } }//function to concatenate the 2nd(back) list at the end of //the 1st(front) list and returns the head of the new list struct Node* concatFrontAndBackList( struct Node *front, struct Node *back) { struct Node *head = front; while (front-> next != NULL) front = front-> next; front-> next= back; return head; }//function to modify the contents of the linked list struct Node* modifyTheList( struct Node *head) { //if list is empty or contains only single node if (!head || head-> next == NULL) return head; struct Node *front, *back; //split the list into two halves //front and back lists frontAndBackSplit(head, & front, & back); //reverse the 2nd(back) list reverseList(& back); //modify the contents of 1st half modifyTheContentsOf1stHalf(front, back); //agains reverse the 2nd(back) list reverseList(& back); //concatenating the 2nd list back to the //end of the 1st list head = concatFrontAndBackList(front, back); //pointer to the modified list return head; }//function to print the linked list void printList( struct Node *head) { if (!head) return ; while (head-> next != NULL) { cout < < head-> data < <" -> " ; head = head-> next; } cout < < head-> data < < endl; }//Driver program to test above int main() { struct Node *head = NULL; //creating the linked list push(& head, 10); push(& head, 7); push(& head, 12); push(& head, 8); push(& head, 9); push(& head, 2); //modify the linked list head = modifyTheList(head); //print the modified linked list cout < < "Modified List:" < < endl; printList(head); return 0; }

Java

//Java implementation to modify the contents //of the linked list class GFG {/* Linked list node */ static class Node { int data; Node next; }; /* Function to insert a node at the beginning of the linked list */ static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = https://www.lsbin.com/new_data; /* link the old list at the end of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head_ref; } static Node front, back; /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. Uses the fast/slow pointer strategy. */ static void frontAndBackSplit( Node head) { Node slow, fast; slow = head; fast = head.next; /* Advance'fast' two nodes, and advance 'slow' one node */ while (fast != null ) { fast = fast.next; if (fast != null ) { slow = slow.next; fast = fast.next; } }/* 'slow' is before the midpoint in the list, so split it in two at that point. */ front = head; back = slow.next; slow.next = null ; }/* Function to reverse the linked list */ static Node reverseList( Node head_ref) { Node current, prev, next; current = head_ref; prev = null ; while (current != null ) { next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; return head_ref; }//perfrom the required subtraction operation //on the 1st half of the linked list static void modifyTheContentsOf1stHalf() { Node front1 = front, back1 = back; //traversing both the lists simultaneously while (back1 != null ) { //subtraction operation and node data //modification front1.data = https://www.lsbin.com/front1.data - back1.data; front1 = front1.next; back1 = back1.next; } }//function to concatenate the 2nd(back) list //at the end of the 1st(front) list and //returns the head of the new list static Node concatFrontAndBackList(Node front, Node back) { Node head = front; if (front == null ) return back; while (front.next != null ) front = front.next; front.next = back; return head; }//function to modify the contents of the linked list static Node modifyTheList( Node head) { //if list is empty or contains only single node if (head == null || head.next == null ) return head; front = null ; back = null ; //split the list into two halves //front and back lists frontAndBackSplit(head); //reverse the 2nd(back) list back = reverseList(back); //modify the contents of 1st half modifyTheContentsOf1stHalf(); //agains reverse the 2nd(back) list back = reverseList(back); //concatenating the 2nd list back to the //end of the 1st list head = concatFrontAndBackList(front, back); //pointer to the modified list return head; }//function to print the linked list static void printList( Node head) { if (head == null ) return ; while (head.next != null ) { System.out.print(head.data +" -> " ); head = head.next; } System.out.println(head.data ); }//Driver Code public static void main(String args[]) { Node head = null ; //creating the linked list head = push(head, 10 ); head = push(head, 7 ); head = push(head, 12 ); head = push(head, 8 ); head = push(head, 9 ); head = push(head, 2 ); //modify the linked list head = modifyTheList(head); //print the modified linked list System.out.println( "Modified List:" ); printList(head); } }//This code is contributed by Arnab Kundu

python

# Python implementation to modify the contents # of the linked list# Linked list node class Node: def __init__( self , data): self .data = https://www.lsbin.com/data self . next = None# Function to insert a node at the beginning # of the linked list def push(head_ref, new_data):# allocate node new_node = Node( 0 )# put in the data new_node.data = new_data# link the old list at the end #of the new node new_node. next = head_ref # move the head to point to the new node head_ref = new_nodereturn head_reffront = None back = None# Split the nodes of the given list # into front and back halves, # and return the two lists # using the reference parameters. # Uses the fast/slow pointer strategy. def frontAndBackSplit( head):global front global back slow = None fast = Noneslow = head fast = head. next# Advance'fast' two nodes, and # advance 'slow' one node while (fast ! = None ):fast = fast. next if (fast ! = None ): slow = slow. next fast = fast. next# 'slow' is before the midpoint in the list, # so split it in two at that point. front = head back = slow. next slow. next = None return head# Function to reverse the linked list def reverseList( head_ref):current = None prev = None next = None current = head_ref prev = None while (current ! = None ):next = current. next current. next = prev prev = current current = nexthead_ref = prev return head_ref# perfrom the required subtraction operation # on the 1st half of the linked list def modifyTheContentsOf1stHalf():global front global back front1 = front back1 = back# traversing both the lists simultaneously while (back1 ! = None ):# subtraction operation and node data # modification front1.data = https://www.lsbin.com/front1.data - back1.datafront1 = front1. next back1 = back1. next# function to concatenate the 2nd(back) list # at the end of the 1st(front) list and # returns the head of the new list def concatFrontAndBackList( front, back):head = frontif (front = = None ): return backwhile (front. next ! = None ): front = front. nextfront. next = back return head# function to modify the contents of the linked list def modifyTheList( head):global front global back# if list is empty or contains only single node if (head = = None or head. next = = None ): return head front = None back = None# split the list into two halves # front and back lists frontAndBackSplit(head)# reverse the 2nd(back) list back = reverseList(back)# modify the contents of 1st half modifyTheContentsOf1stHalf()# agains reverse the 2nd(back) list back = reverseList(back)# concatenating the 2nd list back to the # end of the 1st list head = concatFrontAndBackList(front, back)# pointer to the modified list return head# function to print the linked list def printList( head):if (head = = None ): returnwhile (head. next ! = None ):print (head.data ," -> " , end = "") head = head. nextprint (head.data )# Driver Codehead = None# creating the linked list head = push(head, 10 ) head = push(head, 7 ) head = push(head, 12 ) head = push(head, 8 ) head = push(head, 9 ) head = push(head, 2 )# modify the linked list head = modifyTheList(head)# print the modified linked list print ( "Modified List:" ) printList(head)# This code is contributed by Arnab Kundu

C#

//C# implementation to modify the //contents of the linked list using System; class GFG {/* Linked list node */ public class Node { public int data; public Node next; }; /* Function to insert a node at the beginning of the linked list */ static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = https://www.lsbin.com/new_data; /* link the old list at the end of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head_ref; } static Node front, back; /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. Uses the fast/slow pointer strategy. */ static void frontAndBackSplit( Node head) { Node slow, fast; slow = head; fast = head.next; /* Advance'fast' two nodes, and advance 'slow' one node */ while (fast != null ) { fast = fast.next; if (fast != null ) { slow = slow.next; fast = fast.next; } }/* 'slow' is before the midpoint in the list, so split it in two at that point. */ front = head; back = slow.next; slow.next = null ; }/* Function to reverse the linked list */ static Node reverseList(Node head_ref) { Node current, prev, next; current = head_ref; prev = null ; while (current != null ) { next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; return head_ref; }//perfrom the required subtraction operation //on the 1st half of the linked list static void modifyTheContentsOf1stHalf() { Node front1 = front, back1 = back; //traversing both the lists simultaneously while (back1 != null ) { //subtraction operation and node data //modification front1.data = https://www.lsbin.com/front1.data - back1.data; front1 = front1.next; back1 = back1.next; } }//function to concatenate the 2nd(back) list //at the end of the 1st(front) list and //returns the head of the new list static Node concatFrontAndBackList(Node front, Node back) { Node head = front; if (front == null ) return back; while (front.next != null ) front = front.next; front.next = back; return head; }//function to modify the contents of //the linked list static Node modifyTheList(Node head) { //if list is empty or contains //only single node if (head == null || head.next == null ) return head; front = null ; back = null ; //split the list into two halves //front and back lists frontAndBackSplit(head); //reverse the 2nd(back) list back = reverseList(back); //modify the contents of 1st half modifyTheContentsOf1stHalf(); //agains reverse the 2nd(back) list back = reverseList(back); //concatenating the 2nd list back to the //end of the 1st list head = concatFrontAndBackList(front, back); //pointer to the modified list return head; }//function to print the linked list static void printList( Node head) { if (head == null ) return ; while (head.next != null ) { Console.Write(head.data +" -> " ); head = head.next; } Console.WriteLine(head.data ); }//Driver Code public static void Main() { Node head = null ; //creating the linked list head = push(head, 10); head = push(head, 7); head = push(head, 12); head = push(head, 8); head = push(head, 9); head = push(head, 2); //modify the linked list head = modifyTheList(head); //print the modified linked list Console.WriteLine( "Modified List:" ); printList(head); } }//This code is contributed by PrinciRaj1992

输出如下：

Modified List: -8 -> 2 -> -4 -> 12 -> 7 -> 10

时间复杂度：O(n), 其中?在节点数上。
另一种方法(使用堆栈)：
1.找到下半个链表的起点。
2.将后半列表的所有元素推入堆栈s中。
3.使用temp从头开始遍历列表, 直到堆栈不为空
并通过减去每个节点的堆栈顶部元素来修改temp-> data。
下面是使用堆栈的实现。
C ++

//C++ implementation to modify the //contents of the linked list #include < bits/stdc++.h> using namespace std; //Linked list node struct Node { int data; struct Node* next; }; //function prototype for printing the list void printList( struct Node*); //Function to insert a node at the //beginning of the linked list void push( struct Node **head_ref, int new_data) {//allocate node struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); //put in the data new_node-> data = https://www.lsbin.com/new_data; //link the old list at the end of the new node new_node-> next = *head_ref; //move the head to point to the new node *head_ref = new_node; } //function to print the linked list void printList( struct Node *head) { if (!head) return ; while (head-> next != NULL) { cout < < head-> data < <" -> " ; head = head-> next; } cout < < head-> data < < endl; }//Function to middle node of list. Node* find_mid(Node *head) { Node *temp = head, *slow = head, *fast = head ; while (fast & & fast-> next) {//Advance 'fast' two nodes, and //advance 'slow' one node slow = slow-> next ; fast = fast-> next-> next ; }//If number of nodes are odd then update slow //by slow-> next; if (fast) slow = slow-> next ; return slow ; }//function to modify the contents of the linked list. void modifyTheList( struct Node *head, struct Node *slow) { //Create Stack. stack < int> s; Node *temp = head ; while (slow) { s.push( slow-> data ) ; slow = slow-> next ; }//Traverse the list by using temp until stack is empty. while ( !s.empty() ) { temp-> data = https://www.lsbin.com/temp-> data - s.top() ; temp = temp-> next ; s.pop() ; }}//Driver program to test above int main() { struct Node *head = NULL, *mid ; //creating the linked list push(& head, 10); push(& head, 7); push(& head, 12); push(& head, 8); push(& head, 9); push(& head, 2); //Call Function to Find the starting point of second half of list. mid = find_mid(head) ; //Call function to modify the contents of the linked list. modifyTheList( head, mid); //print the modified linked list cout < <"Modified List:" < < endl; printList(head); return 0; } //This is contributed by Mr. Gera

Java

//Java implementation to modify the //contents of the linked list import java.util.*; class GFG {//Linked list node static class Node {int data; Node next; }; //Function to insert a node at the //beginning of the linked list static Node push(Node head_ref, int new_data) {//allocate node Node new_node = new Node(); //put in the data new_node.data = https://www.lsbin.com/new_data; //link the old list at the end of the new node new_node.next = head_ref; //move the head to point to the new node head_ref = new_node; return head_ref; }//function to print the linked list static void printList(Node head) { if (head == null ) { return ; }while (head.next != null ) { System.out.print(head.data +"-> " ); head = head.next; } System.out.print(head.data + "\n" ); }//Function to middle node of list. static Node find_mid(Node head) { Node temp = head, slow = head, fast = head; while (fast != null & & fast.next != null ) {//Advance 'fast' two nodes, and //advance 'slow' one node slow = slow.next; fast = fast.next.next; }//If number of nodes are odd then update slow //by slow.next; if (fast != null ) { slow = slow.next; }return slow; }//function to modify the contents of the linked list. static void modifyTheList(Node head, Node slow) { //Create Stack. Stack< Integer> s = new Stack< Integer> (); Node temp = head; while (slow != null ) { s.add(slow.data); slow = slow.next; }//Traverse the list by using temp until stack is empty. while (!s.empty()) { temp.data = https://www.lsbin.com/temp.data - s.peek(); temp = temp.next; s.pop(); }}//Driver program to test above public static void main(String[] args) { Node head = null , mid; //creating the linked list head = push(head, 10 ); head = push(head, 7 ); head = push(head, 12 ); head = push(head, 8 ); head = push(head, 9 ); head = push(head, 2 ); //Call Function to Find the starting //point of second half of list. mid = find_mid(head); //Call function to modify //the contents of the linked list. modifyTheList(head, mid); //print the modified linked list System.out.print("Modified List:" + "\n" ); printList(head); } }//This code is contributed by Rajput-Ji

C#

//C# implementation to modify the //contents of the linked list using System; using System.Collections.Generic; class GFG {//Linked list node public class Node {public int data; public Node next; }; //Function to insert a node at the //beginning of the linked list static Node push(Node head_ref, int new_data) {//allocate node Node new_node = new Node(); //put in the data new_node.data = https://www.lsbin.com/new_data; //link the old list at the end of the new node new_node.next = head_ref; //move the head to point to the new node head_ref = new_node; return head_ref; }//function to print the linked list static void printList(Node head) { if (head == null ) { return ; }while (head.next != null ) { Console.Write(head.data +"-> " ); head = head.next; } Console.Write(head.data + "\n" ); }//Function to middle node of list. static Node find_mid(Node head) { Node temp = head, slow = head, fast = head; while (fast != null & & fast.next != null ) {//Advance 'fast' two nodes, and //advance 'slow' one node slow = slow.next; fast = fast.next.next; }//If number of nodes are odd then update slow //by slow.next; if (fast != null ) { slow = slow.next; }return slow; }//function to modify the contents of the linked list. static void modifyTheList(Node head, Node slow) { //Create Stack. Stack< int> s = new Stack< int> (); Node temp = head; while (slow != null ) { s.Push(slow.data); slow = slow.next; }//Traverse the list by using temp until stack is empty. while (s.Count != 0) { temp.data = https://www.lsbin.com/temp.data - s.Peek(); temp = temp.next; s.Pop(); }}//Driver code public static void Main(String[] args) { Node head = null , mid; //creating the linked list head = push(head, 10); head = push(head, 7); head = push(head, 12); head = push(head, 8); head = push(head, 9); head = push(head, 2); //Call Function to Find the starting //point of second half of list. mid = find_mid(head); //Call function to modify //the contents of the linked list. modifyTheList(head, mid); //print the modified linked list Console.Write("Modified List:" + "\n" ); printList(head); } }//This code is contributed by PrinciRaj1992

输出如下：

Modified List: -8 -> 2 -> -4 -> 12 -> 7 -> 10

时间复杂度：O(n)
空间复杂度：O(n/2)
参考文献： https://www.careercup.com/question?id=5657550909341696
【算法设计（修改链表的内容）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  Docker容器下快速搭建Hyperf框架在Windows系统的本地开发环境
• 

  u盘启动快捷键u盘启动快捷键
• 

  吃了止痛药能打新冠疫苗吗
• 

  FGO魔伊复刻流程攻略 魔法少女纪行复刻活动流程推荐
• 

  随性写的
• 

  高三学生经商有前途吗？
• 

  让你的打印机重获新生 益普生打印机废墨清零软件下载
• 

  3000元价位手机怎么选好 3000元价位手机怎么选
• 

  安乐什么意思 安乐是什么意思
• 

  王者荣耀狂铁所有皮肤 王者荣耀狂铁战令皮肤怎么样
• 

  代理服务器出了什么问题？ 代理服务器不能怎么回事
• 

  纵向沟通与横向沟通有何不同 横向沟通与纵向沟通各有哪些优缺点
• 

  吃南瓜子能减肥吗
• 

  圆的面积和底面积一样吗? 圆的面积和底面积一样吗
• 

  手机cpu怎么设置最佳性能
• 

  宫腔镜|不知道宫腔镜有何优势？给你列出这3点，可别小瞧了
• 

  急脾气的妈妈怎么对待慢性子的孩子
• 

  粉扑拿回来要洗吗 粉扑用完怎么放置
• 

  的哥马上要交班，却闯祸又丢工作
• 

  mysql查询前三名 mysql查询第三到第五

• 修改二叉树以仅使用右指针获得先序遍历
• 算法设计（模划分详细实现）
• 模幂（模运算中的幂）
• 算法设计（从1到n的模乘逆）
• 循环冗余校验和Modulo-2分区
• 算法题（模数10 ^ 9 + 7（1000000007））
• 自学一年C#(WPF)，第二年自学Android。登录
• Android性能优化系列之渲染优化
• android studio 学习之一