java java中的单向链表

Singly linked list in java

提问by Simon Kiely

i just found this difficult interview question online and I was hoping someone could help me make sense of it. It is a generic question...given a singly linked list, swap each element of the list in pairs so that 1->2->3->4 would become 2->1->4->3.

我刚刚在网上发现了这个困难的面试问题，我希望有人能帮助我理解它。这是一个通用问题......给定一个单链表，成对交换列表的每个元素，使 1->2->3->4 变成 2->1->4->3。

You have to swap the elements, not the values. The answer should work for circular lists where the tail is pointing back to the head of the list. You do not have to check if the tail points to an intermediate (non-head) element.

您必须交换元素，而不是值。答案应该适用于尾部指向列表头部的循环列表。您不必检查尾部是否指向中间（非头部）元素。

So, I thought:

所以我认为：

public class Node
{
     public int n;     // value
     public Node next; // pointer to next node
}

What is the best way to implement this? Can anyone help?

实现这一点的最佳方法是什么？任何人都可以帮忙吗？

采纳答案by wchargin

I agree with @Stephen about not giving the answer (entirely), but I think I should give you hints.

我同意@Stephen 关于不给出答案（完全）的意见，但我想我应该给你一些提示。

An important thing to understand is that Java does not explicitly specify pointers - rather, whenever a non-primitive (e.g. not char, byte, int, double, float, long, boolean, short) is passed to a function, it is passed as a reference. So, you can use temporary variables to swap the values. Try to code one yourself or look below:

需要理解的重要一点是，Java 没有明确指定指针 - 相反，每当将非原始类型（例如 not char, byte, int, double, float, long, boolean, short）传递给函数时，它都会作为引用传递。因此，您可以使用临时变量来交换值。尝试自己编写代码或查看以下内容：

 public static void swapNodeNexts(final Node n1, final Node n2) {  
    final Node n1Next = n1.next;  
    final Node n2Next = n2.next;  
    n2.next = n1Next;  
    n1.next = n2Next;  
 }  

Then you'll need a data structure to hold the Nodes. It's important that there be an even number of Nodes only (odd numbers unnecessarily complicate things). It's also necessary to initialize the nodes. You should put this in your main method.

然后你需要一个数据结构来保存Nodes。重要的Node是只有偶数个 s（奇数不必要地使事情复杂化）。还需要初始化节点。你应该把它放在你的主要方法中。

  public static final int NUMPAIRS = 3;
 public static void main(final String[] args) {
    final Node[] nodeList = new Node[NUMPAIRS * 2];
    for (int i = 0; i < nodeList.length; i++) {
        nodeList[i] = new Node();
        nodeList[i].n = (i + 1) * 10;
        // 10 20 30 40
    }
    // ...
 } 

The important part is to set the Node next values. You can't just loop through with a forloop for all of them, because then the last one's nextwould throw an IndexOutOfBoundsException. Try to make one yourself, or peek at mine.

重要的部分是设置节点下一个值。你不能只用一个for循环来遍历所有这些，因为最后一个next会抛出一个IndexOutOfBoundsException. 试着自己做一个，或者偷看我的。

  for (int i = 0; i < nodeList.length - 1; i++) {
    nodeList[i].next = nodeList[i + 1];
 }
 nodeList[nodeList.length - 1].next = nodeList[0];

Then run your swap function on them with a forloop. But remember, you don't want to run it on everynode… think about it a bit.

然后用for循环对它们运行交换函数。但是请记住，您不想在每个节点上都运行它……稍微考虑一下。

If you can't figure it out, here is my final code:

如果你无法弄清楚，这是我的最终代码：

 // Node
 class Node {
    public int n; // value
    public Node next; // pointer to next node

    @Override
    public String toString() {
        return "Node [n=" + n + ", nextValue=" + next.n + "]";
    }

 }

 // NodeMain
 public class NodeMain {
    public static final int NUMPAIRS = 3;

    public static void main(final String[] args) {
        final Node[] nodeList = new Node[NUMPAIRS * 2];
        for (int i = 0; i < nodeList.length; i++) {
            nodeList[i] = new Node();
            nodeList[i].n = (i + 1) * 10;
            // 10 20 30 40
        }
        for (int i = 0; i < nodeList.length - 1; i++) {
            nodeList[i].next = nodeList[i + 1];
        }
        nodeList[nodeList.length - 1].next = nodeList[0];

        // This makes 1 -> 2 -> 3 -> 4 -> 1 etc.
        printNodes(nodeList);

        for (int i = 0; i < nodeList.length; i += 2) {
            swapNodeNexts(nodeList[i], nodeList[i + 1]);
        }

        // Now: 2 -> 1 -> 4 -> 3 -> 1 etc.
        printNodes(nodeList);

    }

    private static void printNodes(final Node[] nodeList) {
        for (int i = 0; i < nodeList.length; i++) {
            System.out.println("Node " + (i + 1) + ": " + nodeList[i].n
                    + "; next: " + nodeList[i].next.n);
        }
        System.out.println();
    }

    private static void swapNodeNexts(final Node n1, final Node n2) {
        final Node n1Next = n1.next;
        final Node n2Next = n2.next;
        n2.next = n1Next;
        n1.next = n2Next;
    }
 } 

I hope you were able to figure out at least some of this with guidance. More importantly, however, it's important that you understand the concepts here. If you have any questions, just leave a comment.

我希望你能够在指导下至少弄清楚其中的一些。然而，更重要的是，理解这里的概念很重要。如果您有任何问题，请发表评论。

回答by dareniott

Simple recursive solution in Java:

Java中的简单递归解决方案：

public static void main(String[] args)
{
    Node n = new Node(1);
    n.next = new Node(2);
    n.next.next = new Node(3);
    n.next.next.next = new Node(4);
    n.next.next.next.next = new Node(5);

    n = swap(n);
}
public static Node swap(Node n)
{
    if(n == null || n.next == null)
        return n;
    Node buffer = n;
    n = n.next;
    buffer.next = n.next;
    n.next = buffer;
    n.next.next = swap(buffer.next);
    return n;
 }

public static class Node
{
    public int data; // value
    public Node next; // pointer to next node

    public Node(int value)
    {
        data = value;
    }
}

回答by mdev

Methods needed to run this program :

运行此程序所需的方法：

public static void main(String[] args) {
    int iNoNodes = 10;
    System.out.println("Total number of nodes : " + iNoNodes);
    Node headNode = NodeUtils.createLinkedListOfNElements(iNoNodes);
    Node ptrToSecondNode = headNode.getNext();
    NodeUtils.printLinkedList(headNode);
    reversePairInLinkedList(headNode);
    NodeUtils.printLinkedList(ptrToSecondNode);
}

Approach is almost same, others are trying to explain. Code is self-explainatory.

方法几乎相同，其他人正在尝试解释。代码是不言自明的。

private static void reversePairInLinkedList(Node headNode) {
    Node tempNode = headNode;
    if (tempNode == null || tempNode.getNext() == null)
        return;
    Node a = tempNode;
    Node b = tempNode.getNext();
    Node bNext = b.getNext(); //3
    b.setNext(a);
    if (bNext != null && bNext.getNext() != null)
        a.setNext(bNext.getNext());
    else
        a.setNext(null);
    reversePairInLinkedList(bNext);
}

回答by Nitin Garg

Algo(node n1) -

算法（节点 n1） -

keep 2 pointers n1 and n2, at the current 2 nodes. n1 --> n2 --->...

在当前的 2 个节点上保留 2 个指针 n1 和 n2。n1 --> n2 --->...

• if(n1 and n2 link to each other) return n2;

• if(n1 is NULL) return NULL;

• if(n2 is NULL) return n1;

• if(n1 and n2 do not link to each other and are not null)

• change the pointer of n2 to n1.

• call the algorthm recursively on n2.next

• return n2;

• if(n1 和 n2 相互链接) 返回 n2;

• if(n1 is NULL) 返回 NULL;

• if(n2 is NULL) 返回 n1;

• if(n1 和 n2 不相互链接并且不为空)

• 将 n2 的指针更改为 n1。

• 在 n2.next 上递归调用算法

• 返回 n2；

Code (working) in c++

C++ 中的代码（工作）

#include <iostream>
using namespace std;

class node
{
public:
int value;
node* next;
node(int val);
};

node::node(int val)
{
value = val;
}

node* reverse(node* n)
{

if(n==NULL) return NULL;
node* nxt = (*n).next;
if(nxt==NULL) return n;

if((*nxt).next==n) return nxt;
else
    {
node* temp = (*nxt).next;
(*nxt).next = n;
 (*n).next   = reverse(temp);
}
return nxt;

}
void print(node* n)
{
node* temp = n;
while(temp!=NULL)
    {
    cout<<(*temp).value;
    temp = (*temp).next;
    }
cout << endl;

}

int main()
{
node* n = new node(0);
node* temp = n;

for(int i=1;i<10;i++)
{

node* n1 = new node(i);
(*temp).next = n1;
temp = n1;
}
print(n);
node* x = reverse(n);
print(x);

}

}

回答by cHao

public static Node swapPairs(Node start)
{
    // empty or one-node lists don't need swapping
    if (start == null || start.next == start) return start;

    // any list we return from here on will start at what's the second node atm
    Node result = start.next;

    Node current = start; 
    Node previous = null;     // so we can fix links from the previous pair

    do
    {
        Node node1 = current;
        Node node2 = current.next;

        // swap node1 and node2 (1->2->? ==> 2->1->?)
        node1.next = node2.next;
        node2.next = node1;

        // If prev exists, it currently points at node1, not node2.  Fix that
        if (previous != null) previous.next = node2;

        previous = current;

        // only have to bump once more to get to the next pair;
        // swapping already bumped us forward once
        current = current.next;

    } while (current != start && current.next != start);

    // The tail needs to point at the new head
    // (if current == start, then previous is the tail, otherwise current is)
    ((current == start) ? previous : current).next = result;

    return result;
}

回答by javaMan

public static Node swapInPairs(Node n)
{
    Node two;
    if(n ==null ||n.next.next ==null)
    {
        Node one =n;
        Node twoo = n.next;
        twoo.next = one;
        one.next =null;
        return twoo;            
    }
    else{
        Node one = n;
        two = n.next;   
        Node three = two.next;
        two.next =one;
        Node res = swapInPairs(three);
        one.next =res;          
    }
    return two;
}

I wrote the code at atomic level. So i hope it is self explanatory. I tested it. :)

我在原子级别编写了代码。所以我希望它是不言自明的。我测试了它。:)

回答by Stephen C

The general approach to take is to step through the list, and on every other step you reorder the list nodes by assigning the nodevalues.

采取的一般方法是单步执行列表，并在每隔一步通过分配node值来重新排序列表节点。

But I think you will get more out of this (i.e. learn more) if you actually design, implement and test this yourself. (You don't get a free "phone a friend" or "ask SO" at a job interview ...)

但我认为，如果您自己实际设计、实施和测试它，您会从中获得更多（即了解更多）。（你不会在求职面试中得到免费的“给朋友打电话”或“问 SO”......）

回答by Hot Licks

Yep, write an iterative routine that progresses two links in each iteration. Remember the link from the previous iteration so that you can back-patch it, then swap the current two links. The tricky parts are getting started (to a small extent) and knowing when to finish (to a larger one), especially if you end up having an odd number of elements.

是的，编写一个迭代例程，在每次迭代中推进两个链接。记住上一次迭代中的链接，以便您可以对它进行回补，然后交换当前的两个链接。棘手的部分是开始（在小范围内）并知道何时完成（到更大的部分），尤其是当您最终拥有奇数个元素时。

回答by Rocky

//2.1 , 2.2 Crack the code interview

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct Node{
    int info;
    struct Node *next;
};




 struct Node *insert(struct Node *head,int data){
    struct Node *temp,*ptr;

     temp = (struct Node*)malloc(sizeof(struct Node));
     temp->info=data;
     temp->next=NULL;

     if(head==NULL)
        head=temp;

     else{
        ptr=head;
        while(ptr->next!=NULL)
        {
        ptr=ptr->next;
        }
        ptr->next=temp;
     }
    return head;
 }


 struct Node* reverse(struct Node* head){
    struct Node *current,*prev,*next;
    current = head;
    prev=NULL;
    while(current!=NULL){
        next=current->next;
        current->next = prev;
        prev=current;
        current=next;
    }
    head=prev;
    return head;
}
/*nth till last element in linked list*/

void nthlastElement(struct Node *head,int n){
    struct Node *ptr;
    int last=0,i;
    ptr=head;

    while(ptr!=NULL){
        last++;
        //printf("%d\n",last);
        ptr=ptr->next;
    }

    ptr=head;
    for(i=0;i<n-1;i++){
        ptr=ptr->next;      
    }

    for(i=0;i<=(last-n);i++){
        printf("%d\n",ptr->info);
        ptr=ptr->next;
    }
}

 void display(struct Node* head){
      while(head!=NULL){
        printf("Data:%d\n",head->info);
        head=head->next;
      }
 }



 void deleteDup(struct Node* head){
    struct Node *ptr1,*ptr2,*temp;

    ptr1=head;

    while(ptr1!=NULL&&ptr1->next!=NULL){
            ptr2=ptr1;
          while(ptr2->next!=NULL){
            if(ptr1->info==ptr2->next->info){
                temp=ptr2->next;
                ptr2->next=ptr2->next->next;
                free(temp);
            }
            else{
              ptr2=ptr2->next;
              }

          }  
          ptr1=ptr1->next;
    }
}

 void main(){
    struct Node *head=NULL;
    head=insert(head,10);
    head=insert(head,20);
    head=insert(head,30);
    head=insert(head,10);
    head=insert(head,10);
    printf("BEFORE REVERSE\n"); 
    display(head);
    head=reverse(head);
    printf("AFTER REVERSE\n");
    display(head);
    printf("NTH TO LAST\n");
    nthlastElement(head,2);
     //printf("AFTER DUPLICATE REMOVE\n");
    //deleteDup(head);
    //removeDuplicates(head);
     //display(head);
 }

回答by Andrew Briggs

public class Node
{
     public int n;     // value
     public Node next; // pointer to next node
}

Node[] n = new Node[length];

for (int i=0; i<n.length; i++)
{
    Node tmp = n[i];
    n[i] = n[i+1];
    n[i+1] = tmp;
    n[i+1].next = n[i].next; 
    n[i].next = tmp;
}