交换链表两节点，死循环

Question

题目编号：Exp09-Basic04

题目名称：单链表交换两结点

题目描述：请填写缺失代码完成程序，实现如下功能：

首先根据键盘随机输入，以0结束的若干非零整数建立单链表；

然后根据输入的两个索引位置交换链表上的两个结点（链表首元素索引为1,且要交换的两个索引位置不相邻）；

最后链表各结点值输出，相邻数字间以一个西文空格间隔，最后一个数字后无任何字符。

若是空链表，则输出NULL。

例如，

输入:1 2 3 4 5 6 0 1 5

输出：5 2 3 4 1 6

输入:0 1 2 3 4 5 6 0 1 5

输出：NULL

#include <stdio.h>
#include <malloc.h>
struct cell {
 int x;
 struct cell* next;
};
struct cell* build(void) {
 struct cell* head, * tmp, * p;
 head = tmp = p = NULL;
 int n;
 scanf("%d",&n);
 while(n!=0)
 {
     p=NULL;
     p=(struct cell*)malloc(sizeof(struct cell*));
     p->x=n;
     p->next=NULL;
     if(head==NULL)
     {
         head=p;
         tmp=head;
     }
     else
     {
         tmp->next=p;
         tmp=p;
     }
     scanf("%d",&n);
 }
 return head;
}
struct cell* swap(struct cell* head,int m,int n) {//交换索引为m和n的两个结点，head是单链表首结点指针
 if(head==NULL) return NULL;
    struct cell* pm=head, * pn=head;
 struct cell* pm0 = NULL, * pn0 = NULL;
 struct cell* tmp;
 int i;
 for (i = 1;i < m && pm != NULL;i++) {
  pm0 = pm;
  pm = pm->next;
 }
 for (i = 1;i < n && pn != NULL;i++) {
  pn0 = pn;
  pn = pn->next;
 }
 if (pm != NULL && pn != NULL && m != n) {//索引为m,n的结点位于链表中间

tmp=pm->next;
   pm->next=pn->next;
   pn->next=tmp;
  if (pm0 != NULL && pn0 != NULL) {
   
   pm0->next=pn;
   pn0->next=pm;
   

  }
  if (pm0 == NULL && pn0 != NULL) {
   
   pn0->next=pm;
   head=pn;
   
  

  }
  if (pm0 != NULL && pn0 == NULL) {
    
    pm0->next=pn;
   head=pm;
  
    
  }
 }
 return head;
}
void print(struct cell* head) {
 struct cell*p;
 p=head;
 while(p!=NULL)
 {
     printf(" %d",p->x);
     p=p->next;
 }
}
void release(struct cell* head) {
 struct cell*p;
 while(head!=NULL)
 {
     p=head;
     head=p->next;
     free(p);
 }
}
int main(void) {
 struct cell* head;
 int m, n;
 head = build();
 scanf("%d%d", &m, &n);
 head = swap(head,m,n);
 if(head!=NULL)
        print(head);
    else
        printf("NULL");
 release(head);
}

一直循环
调试时发现，79行带回后，head->next和head->next->next相同

这是为什么呢，谢谢

Answer 1

给你修改好了

#include <stdio.h>
#include <malloc.h>

struct cell
{
    int x;
    struct cell *next;
};

struct cell *build(void)
{
    struct cell *head, *last, *p;
    head = last = p = NULL;
    int n;
    while (1)
    {
        scanf("%d", &n);
        if (n == 0)
            break;
        p = (struct cell *)malloc(sizeof(struct cell));
        p->x = n;
        p->next = NULL;
        if (!head)
            head = p;
        if (last)
            last->next = p;
        last = p;
    }
    return head;
}

struct cell *swap(struct cell *head, int m, int n)
{
    if (!head)
        return NULL;

    // Initial state
    struct cell *prev1 = NULL;
    struct cell *prev2 = NULL;
    struct cell *p1 = head;
    struct cell *p2 = head;
    struct cell *next1 = p1->next;
    struct cell *next2 = p2->next;

    // Find p1 at m
    for (int i = 2; i <= m; i++)
    {
        prev1 = p1;
        p1 = p1->next;
        next1 = p1->next;
    }

    // Find p2 at n
    for (int i = 2; i <= n; i++)
    {
        prev2 = p2;
        p2 = p2->next;
        next2 = p2->next;
    }

    // Insert p2
    if (prev1)
        prev1->next = p2;
    else
        head = p2;
    p2->next = next1;

    // Insert p1
    if (prev2)
        prev2->next = p1;
    else
        head = p1;
    p1->next = next2;

    return head;
}

void print(struct cell *head)
{
    while (head)
    {
        printf(" %d", head->x);
        head = head->next;
    }
}
void release(struct cell *head)
{
    struct cell *p;
    while (head)
    {
        p = head;
        head = head->next;
        free(p);
    }
}

int main(void)
{
    struct cell *head;
    int m, n;
    head = build();
    scanf("%d%d", &m, &n);
    head = swap(head, m, n);
    if (head != NULL)
        print(head);
    else
        printf("NULL");
    release(head);
}