首页 > 代码库 > C/C++链表操作（面试）

C/C++链表操作（面试）

2024-07-13 20:03:25   217人阅读

1.为了反转这个单链表，我们先让头结点的next域指向结点2，再让结点1的next域指向结点3，最后将结点2的next域指向结点1，就完成了第一次交换，顺序就变成了Header-结点2-结点1-结点3-结点4-NULL，然后进行相同的交换将结点3移动到结点2的前面，然后再将结点4移动到结点3的前面就完成了反转，思路有了，就该写代码了：

 1 LinkedList ReverseSinglyLinkedList(LinkedList list) 2 { 3     LNode   *tmp = NULL; 4     LNode   *p = NULL; 5   6     if (list == NULL) 7     { 8         return NULL; 9     }10     tmp = list->next;11     while (tmp->next != NULL)12     {13         p = tmp->next;14         tmp->next = p->next;15         p->next = list->next;16         list->next = p;17     }18     return list;19 }

2.有序单链表的合并就是两个之前都已排好序的链表，将它们合并成一个链表。合并的过程中对于两个链表值相等的结点也要链到最终的链表中去。
 1 struct Node{ 2     int data; 3     Node *next; 4 }; 5  6 typedef struct Node Node; 7  8 Node *Merge(Node *head1,Node *head2) 9 {10     Node *p1 = NULL;11     Node *p2 = NULL;12     Node *head = NULL;13 14     //找出两个链表中第一个结点较小的结点，head记录较小结点的头结点15     if(head1->next->data < head2->next->data)16     {17         head = head1;18         p1 = head1->next;19         p2 = head2->next;20     }21     else22     {23         head = head2;24         p2 = head2->next;25         p1 = head1->next;26     }27 28     Node *pcur = head;29 30     //在两个链表中遍历比较，将值较小的结点链接到pcur结点后31     while(p1 != NULL && p2 != NULL)32     {33         if(p1->data <= p2->data)34         {35             pcur->next = p1;36             pcur = p1;37             p1 = p1->next;38         }39         else40         {41             pcur->next = p2;42             pcur = p2;43             p2 = p2->next;44         }45     }46     //将p1或p2剩余的结点链到pcur之后，完成整个合并的过程47     if(p1 != NULL)48         pcur->next = p1;49     if(p2 != NULL)50         pcur->next = p2;51     52     return head;53 }

 


联系
我们