대체 요소를 역순으로 목록 끝에 추가

Question

a-> x-> b-> y-> c-> z로 연결된 목록이 주어지면 대체 요소를 역순으로 바꾸고 목록의 끝에 추가해야합니다. 즉, a → b → c → z → y → x로 출력하십시오.

나는 O (n) 해를 가지고 있지만 여분의 메모리가 필요하다. 우리는 2 개의리스트를 취하여 각각 대체 원소로 채운다. 그래서 두리스트는 abc와 xyz이다. 그리고 우리는 두 번째리스트를 뒤집어서 처음의 꼬리는 그것이 abczyx가되도록.

제 질문은 제 자리에서 할 수 있습니까? 아니면 같은 다른 알고리즘이 있습니까?

Answer 1

기본 개념 :

스토어 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)의 공간.

Answer 2

이것은 아마존 인터뷰에서 최근에 제기 된 질문입니다. 아이디어가 좋게 보이고 트릭이없는 것 같습니다. 의견

Answer 3

자바 코드 : 여기

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; 

} 

Answer 4

을 물어 주시기 의심의 경우에는 재미 을 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; 
}` 

Answer 5

재귀 모드 로직

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; 
}