给定位置交换链表中的两个元素

Question

我想编写一个函数来交换给定位置的列表元素，例如：

original list:
10-->20-->30-->40-->50-->60

如果我给出位置 3，我希望结果列表为：

10-->20-->40-->30-->50-->60

考虑到我不是要交换元素，而是要交换节点。另外，我已经实现了一个版本，但是使用了一个辅助链表，它可以工作，但我很好奇如何只使用链表的链接来解决这个问题。到目前为止，我有以下内容：

public class Node {
    public int elem;
    public Node next;
    public Nodo(int elem){
        this.elem=elem;
    }
}

public class LinkedList{
    Node first;
    Node front;
    int c;
    public void add(int n){
        Node n=new Node(n);
        if (front==null){
            first=n;
        }
        else{
            front.next=n;
        }
        front=n;
        c++;
    }
 public void print(){
        Node t=first;
        while (t!=null){
            System.out.println(t.e);
            t=t.next;
        }
    }

public void swap(int pos){
            int c=1;
            Node prev=first;
            Node curr=prev.next;
            Node t=null;
            if (curr.next==null) System.out.println("next element is null");
            else{
                while (c<pos){
                    prev=prev.next;
                    curr=curr.next;
                    c++;
                }
                t=curr.next;
                curr.next=prev.next;
                prev.next=t;
            }
        }

public static void main(String[] args) {
        LinkedList l=new LinkedList();
        l.add(10);
        l.add(20);
        l.add(30);
        l.add(40);        
        l.add(50);
        l.add(60);
        l.swap(3);
        l.print();
}

问题是当我运行我的程序要交换的元素之一消失了。我做错了什么？

Answer 1

随着行为的细微变化，这将允许交换两个特定节点的位置。

 public boolean oneHereTheOtherThere(int one, int other)
 {  
     Node prevNode1 = null, prevNode2=null;
     Node n1 = linkedList.element(), n2 = linkedList.element(); //head
     //Find where the nodes are
     while(n1 != null && n1.elem!= one) {  
       prevNode1 = n1;  
       n1= n1.next;  
     }                
     while(n2!= null && n2.elem!= other) {  
        prevNode2 = n2;  
        n2 = n2.next;  
     }      
     //swap them if possible
     if(n1!= null && n2!= null) {  
        if(prevNode1 != null)  
           prevNode1.next = n2;          
        else  
           head = n2;  
        if(prevNode2 != null)  
           prevNode2.next = n1;          
         else  
           head = n1;       

         Node dummy = n1.next;   
         n1.next = n2.next;   
         n2.next = dummy;
         return true;      
     }
  
     return false;
 }

Answer 2

您的代码中的问题是：1) 您正在跟踪错误的 prev 节点； 2）您还需要处理头部情况（pos = 1）； 3) 你还需要交换下一个指针。

public void swap(int pos) {
    Node prev = null;
    Node curr = first;
    for(int c = 1; curr != null && c < pos; c++){
            prev = curr;
            curr = curr.next;
    }
    if (pos <= 0 || curr == null || curr.next == null) {
        System.out.println("Next element is null or pos is invalid");
    }
    else if(prev == null){
        Node t = curr.next;
        curr.next = curr.next.next;
        t.next = first;
        first = t;
    }
    else {
        Node t = curr.next;
        curr.next = curr.next.next;
        t.next = prev.next;
        prev.next = t;
    }
}

给定位置交换链表中的两个元素

Swap two elements from a linked list given a position

java

swap

linked-list