我希望能够维护列表中添加元素的顺序。因此,我在Java中使用了LinkedList
。
现在我想要交换链表中的两个元素。首先,我无法找到LinkedList
的elementAt()
方法。而且,也没有一种方法可以在指定位置添加元素。
我希望能够维护列表中添加元素的顺序。因此,我在Java中使用了LinkedList
。
现在我想要交换链表中的两个元素。首先,我无法找到LinkedList
的elementAt()
方法。而且,也没有一种方法可以在指定位置添加元素。
有一个Collections.swap(List<?> list, int i, int j)
方法可以用来交换List<?>
中的两个元素。还有LinkedList.get(int index)
和LinkedList.add(int index, E element)
(这两个方法都是由interface List
指定的)。所有这些操作的时间复杂度均为O(N)
,因为LinkedList
没有实现RandomAccess
。
请查看LinkedList的Javadocs。
要在index
处找到一个元素,请使用get(int index)
。
要将一个element
放置在特定的index
处,请使用set(int index, Object element)
。
如果你在练习中(比如项目或学校)编写自己的LinkedList类,可以尝试创建两个临时Object变量和两个int变量来保存它们在列表中的位置。然后,使用add(int, Object)方法将第一个变量添加到第二个位置,第二个变量添加到第一个位置。
public class SwapNode {
public static Node head;
public static void main(String[] args) {
SwapNode obj = new SwapNode();
obj.insertAtEnd(5);
obj.insertAtEnd(6);
obj.insertAtEnd(4);
obj.insertAtEnd(7);
obj.insertAtEnd(3);
obj.insertAtEnd(8);
obj.insertAtEnd(2);
obj.insertAtEnd(9);
obj.insertAtEnd(1);
obj.print(head);
System.out.println("*** Swapped ***");
obj.swapElementValue(4, 2);
}
public void swapElementValue(int value1, int value2) {
if (value1 == value2) {
System.out.println("Values same, so no need to swap");
return;
}
boolean found1 = false, found2 = false;
Node node = head;
while (node != null && !(found1 && found2)) {
if (node.data == value1) {
node.data = value2;
found1 = true;
node = node.next;
continue;
}
if (node.data == value2) {
node.data = value1;
found2 = true;
node = node.next;
continue;
}
node = node.next;
}
if (found1 && found2) {
print(head);
} else {
System.out.println("Values not found");
}
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
public void print(Node head) {
Node temp = head;
while(temp != null) {
System.out.print(temp.data);
temp = temp.next;
}
System.out.println();
}
static class Node {
private int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
}
// I tried to reduce time complexity here, in 3 while loops (get() and set() use 4 while loop)
void swapAt(int index1, int index2){ // swapping at index
Node tmp = head;
int count=0;
int min, max; // for future reference to reduce time complexity
if(index1<index2){
min = index1;
max = index2;
}
else{
min = index2;
max = index1;
}
int diff = max - min;
while(min!=count){
tmp= tmp.next;
count++;
}
int minValue = tmp.data;
while(max!=count){
tmp= tmp.next;
count++;
}
int maxValue = tmp.data;
tmp.data = minValue;
tmp = head;
count =0;
while(min!=count){
tmp= tmp.next;
count++;
}
tmp.data = maxValue;
}