링크 된 목록에서 인접한 요소 바꾸기

Question

프로그래밍 인터뷰 사이트를 보면서 링크 된 목록의 인접 요소를 바꿔 코드를 발견했지만 조금 틀린 것으로 나타났습니다. 아래는 코드입니다.

void swap (struct list **list1) 
{ 
    struct list *cur, *tmp, *next; 
    cur = *list1; 
    if (cur && cur->next) 
     *list1 = cur->next; 

    //To make sure that we have at least two more elements to be swapped. 
    while (cur && cur->next) 
    { 
     next = cur->next; 
     tmp = next->next; 
     next->next = cur; 
     //We have to make 1->next as 4 in above example (figure). 

     if (tmp) 
      cur->next = tmp->next; 
     cur = tmp; 
    } 
    return; 
} 

이제 나를위한 조건 if (temp)이 바로 여기에 없습니다. 그 평가가 맞습니까?

우리가 같은 링크 된 목록을 가정 해 봅시다 :

이제 우리의 목표는 같은 링크 된 목록을 만드는 것입니다

1->2->3->4->NULL 

다음 if (temp) 우리의 코드가

2->1->4->3->NULL 

내 걱정되는 경우, 우리는 링크 된리스트의 끝에 null을 할당 할 수 없다.

Answer 1

당신 말이 맞습니다. 이것은 작동하지 않습니다. 목록의 끝에 루프를 만들고, 같은 목록에서 swap을 두 번 실행하면 두 번째 실행이 무한 루프가됩니다. 그것은 수

1. 를 노드의 짝수가 있다면 :

   if(tmp) 
       if (tmp->next) 
        cur->next = tmp->next; 
       else 
        cur->next = tmp; // take care of an add number of nodes 
   else 
       cur->next = NULL; // take care of an even number of nodes 
   

   그것은 마지막 노드 처리됩니다 :

   는 다음 코드로 if (tmp)을 대체,이 어색한 코드를 해결하려면 그 전에 노드 대신에 마지막 점이 NULL인지 확인하십시오.
2. 홀수 개의 노드가있는 경우 cur->next을 확인하면 루프가 종료되기 전에 마지막 노드를 가리켜 야합니다.

Answer 2

NULL (마지막 요소)이 아닌지 테스트합니다. 테스트하지 않으면 프로그램이 목록의 마지막 요소에 대한 NULL 포인터를 따르게됩니다.

tmp = next->next; /* If `next` is the last, `next->next` is NULL. */ 

Answer 3

예, 함수에 버그가있는 것은 당연합니다. cur->next은 모든 경우에 올바르게 업데이트되지 않습니다.

로컬 변수 이름 tmp 및 next은 특히 next의 경우 유용하지 않고 적극적으로 혼동하지 않습니다. 그 이름들은 내가 그 기능을 읽었을 때 무슨 일이 벌어지고 있는지 내 머리 속에서 추적하기가 어렵다.

이름이 node1, node2 및 node3 인 경우 어떤 노드가 조작되고 있는지에 대한 내 그림을 유지하는 것이 좋습니다. 그래도 다른 사람들이 동의하지 않는다면 나는 놀라지 않을 것이다.

다음은 내가 읽을 수있는 기능을 수정 한 것입니다. 더 중요한 것은 정확하다고 믿습니다.

void swap (struct list **head) 
{ 
    struct list *node1 = *head; 
    struct list *node2 = node1 ? node1->next : NULL; 

    // handle degenerate cases 
    if (!node2) { 
     // no elements or only one element on the list 
     // nothing to do... 
     return; 
    }  

    // fix-up list head to what will be the new first node on list 
    *head = node2;   

    // while there are at least 2 more elements to be swapped 
    while (node1 && node2) { 
     struct list* node3 = node2->next; 

     // get a pointer to the node that will be the remainder of the 
     // list after the remainder of the list is processed. 
     // 
     // This will be NULL, node3, or 'node4' depending on whether 
     // there are 0 , 1 or 2+ nodes following node1 and node2 
     struct list* remainder = (node3 && node3->next) ? node3->next : node3; 

     node1->next = remainder; 
     node2->next = node1; 

     // prepare pointers to the next two nodes to be swapped 
     node1 = node3; 
     node2 = node3 ? node3->next : NULL; 
    } 

    return; 
} 

Answer 4

자바 구현

주어 : 1->2->3->4->5->6

로직 1. 먼저 - 1 번째 - 2, 3 번째
Second.next = 2. 제
3. 우선 .next = 따라서 짝수 또는 홀수 번호에 따라 Third.next 업데이트

public ListNode evenOddMerge(ListNode head) { 

     if (head == null || head.next == null) { 
      return head; 
     } 

     ListNode first = head; 
     ListNode second = first.next; 
     ListNode third = null; 

     head = second; 

     while (true) { 

      third = second.next; 

      second.next = first; 

      if (third == null || third.next == null) { 
       first.next = third; 
       break; 
      } 

      first.next = third.next; 

      first = third; 
      second = first.next; 
     } 

     return head; 
    } 

크레딧 :