交换链接列表中的相邻元素

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 

现在我们的目标是使一个链表，如：

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

我担心的是，如果if (temp)有没有在我们的代码，我们不能在链表的末尾分配空值。

Answer 1

你说得对。这不起作用。它会在列表末尾创建一个循环，如果您在同一列表上运行两次swap，则第二次运行将进入无限循环。

要解决这种尴尬的代码，用下面的代码替换if (tmp)：

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 

这将需要的最后节点的护理：

1. 如果有偶数个节点，它使确保最后指向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

Java实现

鉴于：1->2->3->4->5->6

逻辑 1.第一 - 1，二 - 2，第三3
2. Second.next =第一
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; 
    } 

学分：Geeks for Geeks