我剛剛在網上發現了這個困難的面試問題，我希望有人能幫助我理解它。這是一個通用的問題......給出一個單獨的鏈表，交換成對的每個元素，以便1-> 2-> 3-> 4將變成2-> 1-> 4-> 3。java中的單鏈表
您必須交換元素，而不是值。答案應該適用於尾部指向列表頭部的循環列表。您不必檢查尾部是否指向中間（非頭部）元素。
所以，我想：
public class Node
{
public int n; // value
public Node next; // pointer to next node
}
什麼是實現這一目標的最佳方式是什麼？誰能幫忙？
我@Stephen同意關於不給答案（全部），但我想我應該給你的提示。
一個重要的事情要明白的是，Java不顯式地指定指針 - 相反，每當非原語（例如，不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;
}
然後你需要一個數據結構來保存Node秒。重要的是隻有偶數的數字（奇數不必要地使事情複雜化）。還有必要初始化節點。你應該把它放在你的主要方法中。
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循環來循環所有這些循環，因爲最後一個的next會拋出IndexOutOfBoundsException。試着自己做一個，或者偷看我的。
for (int i = 0; i < nodeList.length - 1; i++) {
nodeList[i].next = nodeList[i + 1];
}
nodeList[nodeList.length - 1].next = nodeList[0];
然後對他們有for循環運行的交換功能。但請記住，您不希望每節點上運行它......想一想。
如果你不能弄清楚，這是我的最終代碼：
// 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;
}
}
我希望你能找出至少一些這方面的指導。然而更重要的是，你理解這裏的概念很重要。如果您有任何問題，請發表評論。
保存節點的數據結構？鏈接列表如何？奇數個節點「使事情複雜化」？這是一個「面試」問題：讓我們繼續前進，並假設偶爾該工作可能會變得複雜。 –
@Dave：是的，你對併發症是正確的。但是，這個問題也有很多解釋。最後一個會保持不變嗎？它會鏈接到什麼？正因爲如此（並且在問題中沒有提到這個可能性），我試圖簡化這個過程，以向提問者提供關於如何處理這個問題的總體思路。把它當作對他的練習。我不確定你的意思是「關於一個鏈表」 - 如果你指的是'java.util.LinkedList'，我試圖避免這一點，因爲理解這些工作是很重要的，但是是的在實際情況下，它會更合適。 – wchargin
不，我說你不需要在數組中保存一個鏈表，你已經有了一個鏈表。 –
一般採用的方法是遍歷列表，並在其他每一步通過分配node值來重新排列列表節點。
但是我認爲如果你自己實際設計，實施和測試這個，你會得到更多的結果（即瞭解更多）。 （你沒有在求職面試中獲得免費的「電話朋友」或「詢問SO」）
是的，寫一個迭代例程，在每次迭代中進行兩個鏈接。記住先前迭代的鏈接，以便您可以對其進行修補，然後交換當前的兩個鏈接。棘手的部分是開始（很小程度），並知道何時完成（到更大的一個），特別是如果你最終有奇數個元素。
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;
}
-1。首先，您只需提供代碼而不必進行解釋。其次，在Java中，所有代碼都必須在一個類中（所以第一個'}'以外的所有內容都是無效的）。第三，「長度」在哪裏申報？第四，什麼是'length1111'？第五，即使這些被糾正，這也不會產生正確的輸出。 – wchargin
另一個-1（精神上，我沒有心），因爲這個數組是什麼？ –
@DaveNewton你將如何迭代遍歷節點而不將它們放入像數組這樣的數據結構中 –
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;
}
我在原子級編寫了代碼。所以我希望這是自我解釋。我測試了它。 :)
ALGO（節點N1） -
保持2點指針n1和n2，在目前的2個節點。 n1 - > n2 ---> ...
if（n1和n2相互連接）返回n2;
if（n1爲NULL）返回NULL;
if（n2是NULL）return n1;
如果（n1和n2不鏈接，彼此不爲null）
變化N2的指針N1。
通話n2.next
回報N2的algorthm遞歸;
代碼Java中（工作）在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);
}
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;
}
簡單的遞歸解決方案：
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;
}
}
方法需要運行這個程序：
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);
}
方法是幾乎相同的，其他人都試圖解釋。代碼是自我解釋的。
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);
}
//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);
}
你有什麼這麼遠嗎？ ：D –
這是一個面試問題，而不是作業？有趣。 – corsiKa
什麼是downvote？這是一個有效的問題，它也很有趣... upvoting。 – wchargin