# 算法设计：修改链表的内容

2021年5月3日17:09:08 发表评论 780 次浏览

## 本文概述

n个节点。修改前半节点的值, 以使第一个节点的新值等于最后一个节点的值减去第一个节点的当前值, 第二个节点的新值等于后一个节点的值减去第二个节点的当前值, 对于前半节点也是如此。如果n如果为奇数, 则中间节点的值保持不变。

(没有多余的内存可以使用)。

``````Input : 10 -> 4 -> 5 -> 3 -> 6
Output : 4 -> 1 -> 5 -> 3 -> 6

Input : 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
#include <bits/stdc++.h>
using namespace std;

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
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 = new_data;

/* link the old list at the end of the new node */

/* move the head to point to the 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;

/* Advance 'fast' two nodes, and
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. */
*back_ref = slow->next;
slow->next = NULL;
}

/* Function to reverse the linked list */
{
struct Node *current, *prev, *next;
prev = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}

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

while (front->next != NULL)
front = front->next;

front->next    = back;

}

//function to modify the contents of the linked list
struct Node* modifyTheList( struct Node *head)
{
//if list is empty or contains only single node

struct Node *front, *back;

//split the list into two halves
//front and back lists

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

//pointer to the modified list
}

//function to print the linked list
{
return ;

{
cout <<head->data <<" -> " ;
}
}

//Driver program to test above
int main()
{

cout <<"Modified List:" <<endl;
return 0;
}``````

## Java

``````//Java implementation to modify the contents
class GFG
{

static class Node
{
int data;
Node next;
};

/* Function to insert a node at the beginning
static Node push(Node head_ref, int new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in the data */
new_node.data = new_data;

/* link the old list at the end
of the new node */

/* move the head to point to the new node */

}

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. */
{
Node slow, fast;

/* Advance 'fast' two nodes, and
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. */
back = slow.next;
slow.next = null ;
}

/* Function to reverse the linked list */
{
Node current, prev, next;
prev = null ;
while (current != null )
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}

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

if (front == null ) return back;

while (front.next != null )
front = front.next;

front.next = back;

}

//function to modify the contents of the linked list
{
//if list is empty or contains only single node
front = null ; back = null ;

//split the list into two halves
//front and back lists

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

//pointer to the modified list
}

//function to print the linked list
{
return ;

{
System.out.print(head.data + " -> " );
}
}

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

System.out.println( "Modified List:" );
}
}

//This code is contributed by Arnab Kundu``````

## python

``````# Python implementation to modify the contents

class Node:

def __init__( self , data):
self .data = data
self . next = None

# Function to insert a node at the beginning

# 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

# move the head to point to the new node

front = 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.

global front
global back
slow = None
fast = None

# Advance 'fast' two nodes, and
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.
back = slow. next
slow. next = None

# Function to reverse the linked list

current = None
prev = None
next = None
prev = None
while (current ! = None ):

next = current. next
current. next = prev
prev = current
current = next

# 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 = 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
def concatFrontAndBackList( front, back):

if (front = = None ):
return back

while (front. next ! = None ):
front = front. next

front. next = back

# function to modify the contents of the linked list

global front
global back

# if list is empty or contains only single node
if (head = = None or head. next = = None ):
front = None
back = None

# split the list into two halves
# front and back lists

# 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

# pointer to the modified list

# function to print the linked list

if (head = = None ):
return

while (head. next ! = None ):

print (head.data , " -> " , end = "")

# Driver Code

# print the modified linked list
print ( "Modified List:" )

# This code is contributed by Arnab Kundu``````

## C#

``````//C# implementation to modify the
using System;

class GFG
{

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 = new_data;

/* link the old list at the end
of the new node */

/* move the head to point to the new node */

}

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. */
{
Node slow, fast;

/* Advance 'fast' two nodes, and
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. */
back = slow.next;
slow.next = null ;
}

/* Function to reverse the linked list */
{
Node current, prev, next;
prev = null ;
while (current != null )
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}

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

if (front == null )
return back;

while (front.next != null )
front = front.next;

front.next = back;

}

//function to modify the contents of
{
//if list is empty or contains
//only single node
front = null ; back = null ;

//split the list into two halves
//front and back lists

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

//pointer to the modified list
}

//function to print the linked list
{
return ;

{
Console.Write(head.data + " -> " );
}
}

//Driver Code
public static void Main()
{

Console.WriteLine( "Modified List:" );
}
}

//This code is contributed by PrinciRaj1992``````

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

1.找到下半个链表的起点。

2.将后半列表的所有元素推入堆栈s中。

3.使用temp从头开始遍历列表, 直到堆栈不为空

## C ++

``````//C++ implementation to modify the
#include <bits/stdc++.h>
using namespace std;

struct Node
{
int data;
struct Node* next;
};

//function prototype for printing the list
void printList( struct Node*);

//Function to insert a node at the
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 = new_data;

//link the old list at the end of the new node

//move the head to point to the new node
}

//function to print the linked list
{
return ;

{
cout <<head->data <<" -> " ;
}
}

//Function to middle node of list.
{

while (fast && fast->next)
{

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;

while (slow)
{
s.push( slow->data ) ;
slow = slow->next ;
}

//Traverse the list by using temp until stack is empty.
while ( !s.empty() )
{
temp->data = temp->data - s.top() ;
temp = temp->next ;
s.pop() ;
}

}

//Driver program to test above
int main()
{
struct Node *head = NULL, *mid ;

//Call Function to Find the starting point of second half of list.

//Call function to modify the contents of the linked list.

cout <<"Modified List:" <<endl;
return 0;
}

//This is contributed by Mr. Gera``````

## Java

``````//Java implementation to modify the
import java.util.*;

class GFG
{

static class Node
{

int data;
Node next;
};

//Function to insert a node at the
static Node push(Node head_ref, int new_data)
{

//allocate node
Node new_node = new Node();

//put in the data
new_node.data = new_data;

//link the old list at the end of the new node

//move the head to point to the new node
}

//function to print the linked list
{
{
return ;
}

{
}
}

//Function to middle node of list.
{

while (fast != null && fast.next != null )
{

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>();

while (slow != null )
{
slow = slow.next;
}

//Traverse the list by using temp until stack is empty.
while (!s.empty())
{
temp.data = temp.data - s.peek();
temp = temp.next;
s.pop();
}

}

//Driver program to test above
public static void main(String[] args)
{
Node head = null , mid;

//Call Function to Find the starting
//point of second half of list.

//Call function to modify
//the contents of the linked list.

System.out.print( "Modified List:" + "\n" );
}
}

//This code is contributed by Rajput-Ji``````

## C#

``````//C# implementation to modify the
using System;
using System.Collections.Generic;

class GFG
{

public class Node
{

public int data;
public Node next;
};

//Function to insert a node at the
static Node push(Node head_ref, int new_data)
{

//allocate node
Node new_node = new Node();

//put in the data
new_node.data = new_data;

//link the old list at the end of the new node

//move the head to point to the new node
}

//function to print the linked list
{
{
return ;
}

{
}
}

//Function to middle node of list.
{

while (fast != null && fast.next != null )
{

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>();

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 = temp.data - s.Peek();
temp = temp.next;
s.Pop();
}

}

//Driver code
public static void Main(String[] args)
{
Node head = null , mid;

//Call Function to Find the starting
//point of second half of list.

//Call function to modify
//the contents of the linked list.

Console.Write( "Modified List:" + "\n" );
}
}

//This code is contributed by PrinciRaj1992``````

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