如何在 Java 中交换链表中的两个元素?
原文:https://www . geesforgeks . org/how-swap-two-elements-in-a-linked list-in-Java/
给定一个链表,任务是在不干扰两个元素链接的情况下交换它们。有多种交换方式。通过交换节点内部的元素和交换完整的节点,可以使用交换元素。
例:
Input :- 10->11->12->13->14->15
element1 = 11
element2 = 14
Output :- 10->14->12->13->11->15
方法 1:使用内置设置方法
下面是上述方法的代码:
T3】JavaT5
// Swaping two elements in a Linked List in Java
import java.util.*;
class GFG {
public static void main(String[] args)
{
LinkedList<Integer> ll = new LinkedList<>();
// Adding elements to Linked List
ll.add(10);
ll.add(11);
ll.add(12);
ll.add(13);
ll.add(14);
ll.add(15);
// Elements to swap
int element1 = 11;
int element2 = 14;
System.out.println("Linked List Before Swaping :-");
for (int i : ll) {
System.out.print(i + " ");
}
// Swapping the elements
swap(ll, element1, element2);
System.out.println();
System.out.println();
System.out.println("Linked List After Swaping :-");
for (int i : ll) {
System.out.print(i + " ");
}
}
// Swap Function
public static void swap(LinkedList<Integer> list,
int ele1, int ele2)
{
// Getting the positions of the elements
int index1 = list.indexOf(ele1);
int index2 = list.indexOf(ele2);
// Returning if the element is not present in the
// LinkedList
if (index1 == -1 || index2 == -1) {
return;
}
// Swapping the elements
list.set(index1, ele2);
list.set(index2, ele1);
}
}
T6T8输出T1
时间复杂度: O(N),其中 N 为链表的长度
方法 2:使用我们自己的链表
给定一个链表,提供两个值,用两个给定的节点交换节点。
下面是上述方法的实现:
T3】JavaT5
// Java Program to Swap Two Elements in a LinkedList
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
class LinkedList {
Node head; // head of list
// Function to swap Nodes x and y in
// linked list by changing links
public void swapNodes(int x, int y)
{
// Nothing to do if x and y are same
if (x == y)
return;
// Search for x (keep track of prevX and CurrX)
Node prevX = null, currX = head;
while (currX != null && currX.data != x) {
prevX = currX;
currX = currX.next;
}
// Search for y (keep track of prevY and currY)
Node prevY = null, currY = head;
while (currY != null && currY.data != y) {
prevY = currY;
currY = currY.next;
}
// If either x or y is not present, nothing to do
if (currX == null || currY == null)
return;
// If x is not head of linked list
if (prevX != null)
prevX.next = currY;
else // make y the new head
head = currY;
// If y is not head of linked list
if (prevY != null)
prevY.next = currX;
else // make x the new head
head = currX;
// Swap next pointers
Node temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}
// Function to add Node at beginning of list.
public void push(int new_data)
{
// 1\. alloc the Node and put the data
Node new_Node = new Node(new_data);
// 2\. Make next of new Node as head
new_Node.next = head;
// 3\. Move the head to point to new Node
head = new_Node;
}
// This function prints contents of linked
// list starting from the given Node
public void printList()
{
Node tNode = head;
while (tNode != null) {
System.out.print(tNode.data + " ");
tNode = tNode.next;
}
System.out.println();
}
// Driver program to test above function
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
// The constructed linked list is:
// 1->2->3->4->5->6->7
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Linked List Before Swaping :-");
llist.printList();
llist.swapNodes(4, 3);
System.out.println("Linked List After Swaping :-");
llist.printList();
}
}
T6T8输出T1
时间复杂度: O(N),其中 N 为链表的长度
版权属于:月萌API www.moonapi.com,转载请注明出处