本文概述
- 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
在亚马逊采访中问
方法:以下步骤是:
- 从中间拆分列表。执行前后拆分。如果元素的数量为奇数, 则多余的元素应放在第一(前)列表中。
- 反转第二个(后退)列表.
- 同时遍历两个列表时, 请执行所需的减法操作。
- 再次反转第二个列表。
- 将第二个列表连接回第一个列表的末尾。
//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
【算法设计(修改链表的内容)】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 修改二叉树以仅使用右指针获得先序遍历
- 算法设计(模划分详细实现)
- 模幂(模运算中的幂)
- 算法设计(从1到n的模乘逆)
- 循环冗余校验和Modulo-2分区
- 算法题(模数10 ^ 9 + 7(1000000007))
- 自学一年C#(WPF),第二年自学Android。登录
- Android性能优化系列之渲染优化
- android studio 学习之一