用Java实现的链表中的交换对元素

swap pair elements in linked list implemented in Java

提问by eagertoLearn

I have written a code to swapelements of linkedListin Java. Currently, my code fails, i.e., it is not swappingelements. I am having difficulty on how to approach to this problem. Any tips?

我已经swap为linkedListin 的元素编写了代码Java。目前，我的代码失败，即它不是swapping元素。我在如何解决这个问题上遇到了困难。有小费吗？

public void switchPairs(){
    if (front==null || front.next==null)
        return ;
    ListNode temp=front;
    front=front.next;
    ListNode curr=front;
    while(curr.next!=null){
        ListNode dummy = curr.next;
        curr.next=temp;
        temp.next=dummy;
        temp=temp.next;
        curr=dummy;
    }
}

Input          : front -> [3] -> [7] -> [4] -> [9] -> [8] -> [12] / 
Expected output: front -> [7] -> [3] -> [9] -> [4] -> [12] -> [8] /     
my output:       front -> [7] -> [3] -> [4] -> [9] -> [8] -> [12] /

采纳答案by brain storm

The way I approach this problem is

我处理这个问题的方式是

1. Draw the linkedListfor the inputand desired outputin the right format for the simplest case. Here I would start with 4 nodes;

2. Then tackle the easy cases such as if the ListNodeor the nextis null

3. On the paper, mark the links that are broken and that are formed. Note you have to do the breaking and linking in right order; Make sure you have referenceto the nodeswhose link you are breaking. otherwise you might end up losing some nodes. That is the whole crux here. Draw after each step when a node is broken or a link is formed. In this way, you can keep track of what is going;

4. Translate what you have drawn on paper to code. That must be fairly straightforward! Often you would need to have temporary pointers to traverse the list;

5. In this example, the frontor headpointer needs to be changed. so I would do the first swap outside an iteration. The remaining changes I would inside a while loop.

6. write a convienient toStringmethod that can help you track the variables at each stage. I found it harder to use debuggersforrecusionsand linkedLists. but that is just me.

1. 对于最简单的情况，以正确的格式绘制linkedListforinput和 desired output。在这里，我将从 4 个节点开始；

2. 然后处理简单的情况，例如 if the ListNodeor the nextis null

3. 在纸上，标记断开和形成的链接。请注意，您必须按正确的顺序进行断开和链接；请确保您有reference在nodes其链接你破坏了。否则你最终可能会丢失一些节点。这就是这里的全部症结所在。当节点断开或形成链接时，在每一步之后绘制。通过这种方式，您可以跟踪正在发生的事情；

4. 将您在纸上绘制的内容转换为代码。那一定是相当简单的！通常你需要有临时指针来遍历列表；

5. 在这个例子中，frontorhead指针需要改变。所以我会在迭代之外进行第一次交换。其余的更改我会在while loop.

6. 编写一个方便的toString方法，可以帮助您跟踪每个阶段的变量。我发现它更难debuggers用于recusionsand linkedLists。但是，这只是我。

Regarding the solution for this problem: This is not as easy problem in my opinion. but a good one to get a good grasp of linkedLists andPointers`

关于这个问题的解决方案：在我看来，这不是一个简单的问题。但很好地掌握linkedLists and指针`

here is my solution:

这是我的解决方案：

public void switchPairs(){
    if (front==null || front.next==null)
        return ;
    //keep a pointer to next element of front
    ListNode current=front.next;
    //make front point to next element
    front.next=current.next;
    current.next=front;
    front=current;
    //current has moved one step back it points to first.
    //so get it to the finished swap position
    current=current.next;
    while(current.next!=null && current.next.next!=null){
        ListNode temp = current.next.next;
        current.next.next=temp.next;
        temp.next=current.next;
        current.next=temp;
        current=temp.next;
    }
}

回答by Bhaskar

The best way to answer a question like this to to visualize the state of your list as it progresses thru the iteration. I have implemented the code with a println to help with that. The other choice is to include variable names that are easier to keep track of, while tempand dummywill not prevent you from achieving correctness they are more difficult to follow.

回答此类问题的最佳方法是在迭代过程中可视化列表的状态。我已经用 println 实现了代码来帮助解决这个问题。另一种选择是，包括变量名更易于跟踪，同时temp并dummy不会阻止你实现正确性它们更难以遵循。

This is the function

这是功能

    public ListNode switchPairs(){
        if (this==null || this.next==null)
            return this;
        ListNode top = this.next;

        ListNode first = this;
        ListNode second = first.next;

        do {
            ListNode third = second.next;
            second.next = first;
            first.next = third;
            first = third;
            System.out.println("@@@ " + top.toString());
            if (first != null) {
                // remember second now is really the first element on the list
                // at this point.
                second.next.next = first.next;
                second = first.next;
            }

        } while(first != null && second != null);

        return top;
    }

And this is the entire code

这是整个代码

public class ListNode {
    private ListNode next = null;
    private final int i;
    ListNode(int i) {
        this.i = i;
    }

    ListNode(int i, ListNode parent) {
        this(i);
        parent.next = this;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[" + this.i + "]");
        if (this.next != null) {
            sb.append("->");
            sb.append(this.next.toString());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        ListNode top = null;
        ListNode curr = null;
        for(String arg : args) {
            int i = Integer.parseInt(arg);
            if(curr == null) 
                curr = new ListNode(i);
            else
                curr = new ListNode(i, curr);
            if( top == null) 
                top = curr;
        }
        System.out.println(top.toString());
        top = top.switchPairs();
        System.out.println(top.toString());
    }

    public ListNode switchPairs(){
        if (this==null || this.next==null)
            return this;
        ListNode top = this.next;

        ListNode first = this;
        ListNode second = first.next;

        do {
            ListNode third = second.next;
            second.next = first;
            first.next = third;
            first = third;
            System.out.println("@@@ " + this.toString());
            if (first != null) {
                second.next.next = first.next;
                second = first.next;
            }

        } while(first != null && second != null);

        return top;
    }
}

Last but not least a sample output

最后但并非最不重要的一个示例输出

java ListNode 1 2 3 4 5 6 7 8
[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[3]->[4]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[5]->[6]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[6]->[5]->[7]->[8]
@@@ [2]->[1]->[4]->[3]->[6]->[5]->[8]->[7]
[2]->[1]->[4]->[3]->[6]->[5]->[8]->[7]

回答by wholfeld

public void switchPairs() {
   ListNode prev = front;
    if(front!=null && front.next != null) {
        ListNode temp = front;
        front = front.next;
        temp.next = front.next;
        front.next = temp;
        prev = temp;
    }
    while(prev !=null && prev.next != null && prev.next.next != null) {
        ListNode first_node =prev.next;
        ListNode second_node = first_node.next;
        first_node.next = second_node.next;
        second_node.next = first_node;
        prev.next = second_node;
        prev = first_node;
    }
}

回答by user3676691

public static LinkedList<Integer> switchPairs(LinkedList list) { ListIterator<Integer> iterator = list.listIterator(); LinkedList<Integer> out = null; while (iterator != null && iterator.hasNext()) { if (out == null) { out = new LinkedList<Integer>(); } int temp = iterator.next(); if (iterator.hasNext()) { out.add(iterator.next()); out.add(temp); }else{ out.add(temp); } } return out; }

public static LinkedList<Integer> switchPairs(LinkedList list) { ListIterator<Integer> iterator = list.listIterator(); LinkedList<Integer> out = null; while (iterator != null && iterator.hasNext()) { if (out == null) { out = new LinkedList<Integer>(); } int temp = iterator.next(); if (iterator.hasNext()) { out.add(iterator.next()); out.add(temp); }else{ out.add(temp); } } return out; }

回答by Ali Katkar

// Recursive solution
public void switchPairs(SingleLinkListNode prev, SingleLinkListNode node) {

    if (node == null || node.next == null) {
        return;
    }
    SingleLinkListNode nextNode = node.next;
    SingleLinkListNode temp = nextNode.next;
    nextNode.next = node;
    node.next = temp;
    if (prev != null) {
        prev.next = nextNode;
    } else {
        head = nextNode;
    }

    switchPairs(node, node.next);
}

回答by Shravan J Kumar

I have this recursive function, which works:

我有这个递归函数，它有效：

    public void swap2List(){
    root = swap2List(root);   //pass the root node
    }   
    private Node swap2List(Node current){
    if(current == null || current.next == null){
    return current;
    }
    else{
    Node temp = current;
    Node temp2 = current.next.next;
    current = current.next;
    current.next = temp;
    temp.next = swap2List(temp2);       
    } 
    return current;
    }