反向交替元素並附加到列表的末尾

給定鏈接列表爲a-> x-> b-> y-> c-> z，我們需要反向交替元素並追加到列表的末尾。也就是說，將其輸出爲a-> b-> c-> z-> y-> x。反向交替元素並附加到列表的末尾

我有一個O（n）的解決方案，但它需要額外的內存，我們需要2個列表並分別填充替代元素，因此這兩個列表是abc和xyz，然後我們將反轉第二個列表並將其附加到第一個的尾巴，使它變成abczyx。

我的問題是我們可以做到嗎？或者還有其他的算法嗎？

2014-02-07 h4ck3d

的基本思想：

商店x。
品牌a指向b。
使y指向存儲的元素（x）。
品牌b指向c。
等
最後，將奇數位置上的最後一個元素指向存儲的元素。

僞代碼：（簡化的結束名單檢查爲可讀性）

current = startOfList 
stored = NULL 
while !endOfList 
    temp = current.next 
    current.next = current.next.next 
    temp.next = stored 
    stored = temp 
    current = current.next 
current.next = stored

複雜性：

O（n）的時間，O（1）的空間。

來源

2014-02-07 08:22:46 Dukeling

這是亞馬遜採訪最近的一個問題，Idea看起來不錯，而且似乎沒有任何竅門。

來源

2014-02-09 18:48:06

Java代碼註釋：

static void change(Node n) 
{ 
    if(n == null) 
      return; 

    Node current = n; 

    Node next = null, prev = null; 

    while(current != null && current.next != null) 
    { 
     // One of the alternate node which is to be reversed. 
     Node temp = current.next; 

     current.next = temp.next; 

     // Reverse the alternate node by changing its next pointer. 
     temp.next = next; 

     next = temp; 

     // This node will be used in the final step 
     // outside the loop to attach reversed nodes. 
     prev = current; 

     current = current.next;    
    } 

    // If there are odd number of nodes in the linked list. 
    if(current != null) 
     prev = current; 

    // Attach the reversed list to the unreversed list. 
    prev.next = next; 

}

來源

2014-02-11 17:12:42

這裏不使用任何額外的空間用於任何疑問的情況下做this..enjoy和樂趣隨時問

C代碼

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

    int n; 
    struct link 

    { 
    int val; 
    struct link *next; 
    }; 



void show(struct link *); 

void addatbeg(struct link **p,int num) 
{ 
struct link *temp,*help; 
help=*p; 
temp=(struct link *)malloc(sizeof(struct link)); 
temp->val=num; 
temp->next=NULL; 
    if(help==NULL) 
    { 
    *p=temp; 
    } 
    else 
    { 
    temp->next=help; 
    *p=temp; 
    } 
    n++; 
show(*p); 
} 

void revapp(struct link **p) 
{ 
struct link *temp,*help,*q,*r; 
r=NULL; 
temp=*p; 
help=*p; 

while(temp->next!=NULL) 
{ 

    temp=temp->next; 
    q=r;      //this portion will revrse the even position numbers 
    r=temp; 

    temp=temp->next; 

    //for making a connection between odd place numbers 
    if(help->next->next!=NULL) 
    { 
    help->next=temp; 
    help=help->next; 
    r->next=q; 

    } 

    else 
    { 
     r->next=q; 
     help->next=r; 
     show(*p); 
    return; 
    } 
} 

} 

void show(struct link *q) 
{ 
    struct link *temp=q; 
    printf("\t"); 
    while(q!=NULL) 
    { 

    printf("%d ->",q->val); 
    q=q->next; 
    if(q==temp) 
    { 
    printf("NULL\n"); 
    return; 
    } 
    } 
    printf("NULL\n"); 
} 

int main() 
{ 
n=0; 
struct link *p; 
p=NULL; 

// you can take user defined input but here i am solving it on predefined list 
addatbeg(&p,8); 
addatbeg(&p,7); 
addatbeg(&p,6); 

addatbeg(&p,5); 
addatbeg(&p,4); 

addatbeg(&p,3); 
addatbeg(&p,2); 
addatbeg(&p,1); 


revapp(&p); 

return 0; 
}`

來源

2014-09-30 09:38:56

以下是在遞歸模式邏輯

public static Node alRev(Node head) 
{ 
    if (head == null) return head;  
    if (head.next != null) 
    { 
     if (head.next.next != null) 
     { 
      Node n = head.next; 
      head.next = head.next.next; 
      n.next = null; 
      Node temp = alRev(head.next); 
      if (temp != null){ 
       temp.next = n; 
       return n; 
      }   
     } 
     else 
      return head.next; 
    } 
    else 
     return head; 
    return null; 
}

來源

2018-01-04 13:53:03

反向交替元素並附加到列表的末尾

回答

相關問題