链表习题精选（持续更新中）

第一题

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

struct ListNode* oddEvenList(struct ListNode* head)
{if (head == NULL){return head;}struct ListNode* odd = head;//直接把奇数的第一个作为奇数组头节点struct ListNode* even = head->next;//把偶数的第一个作为偶数组头节点struct ListNode* evenHead = even;while (even != NULL && even->next != NULL){odd->next = even->next;odd = odd->next;even->next = odd->next;even = even->next;}odd->next = evenHead;把偶数组接在奇数组之后return head;}

思考：此处的even != NULL && even->next != NULL能否调换？

答案是不可以，因为此处通过&&的短路现象避免一些访问空指针的错误

第二题

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}else if(list2==NULL){return list1;}struct ListNode* newHead=list1;struct ListNode* cur2=list2;struct ListNode* cur1=list1;if(list1->val>list2->val){newHead=list2;cur2=cur2->next;}else{cur1=cur1->next;}struct ListNode* cur=newHead;while(cur1!=NULL&&cur2!=NULL){if(cur1->val<cur2->val){cur->next=cur1;cur=cur->next;cur1=cur1->next;}else{cur->next=cur2;cur=cur->next;cur2=cur2->next;}}if(cur1==NULL){cur->next=cur2;}else{cur->next=cur1;}return newHead;
}

本题主要是需要考虑情况完备，以及新手在编程时一定不要吝啬于多创建一个常量进行记录，能够让思路清晰很多

当然本题也可以通过带哨兵位的链表，当然思路大差不差，时间复杂度也都是O（n），空间复杂度依然为O（1）。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{    if (list1 == NULL){return list2;}else if (list2 == NULL){return list1;}struct ListNode* dummyHead = malloc(sizeof(struct ListNode));dummyHead->val = 0;struct ListNode* cur = dummyHead, * cur1 = list1, * cur2 = list2;while (cur1 != NULL && cur2 != NULL){if (cur1->val <= cur2->val){cur->next = cur1;cur1 = cur1->next;cur = cur->next;}else{cur->next = cur2;cur2 = cur2->next;cur = cur->next;}}if (cur1 != NULL){cur->next = cur1;}else if (cur2 != NULL){cur->next = cur2;}struct ListNode* ret = dummyHead->next;free(dummyHead);return ret;
}

第三题，排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

方法一：自顶向下归并排序

对链表自顶向下归并排序的过程如下。

第1步.找到链表的中间，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针（快二慢一）当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。对两个子链表分别排序。

第2步.不断递归向下二分后，对最小的两个子链表分别排序合并

第3步.将最后两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

//合并函数，因为递归的地方已经解决了传入链表为空的问题，故可以不进行NULL的判断
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead = malloc(sizeof(struct ListNode));dummyHead->val = 0;struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;while (temp1 != NULL && temp2 != NULL) {if (temp1->val <= temp2->val) {temp->next = temp1;temp1 = temp1->next;} else {temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if (temp1 != NULL) {temp->next = temp1;} else if (temp2 != NULL) {temp->next = temp2;}return dummyHead->next;
}
//实现递归并终止的递归的函数
struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {if (head == NULL) {return head;}if (head->next == tail) {head->next = NULL;return head;}struct ListNode *slow = head, *fast = head;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;}}struct ListNode* mid = slow;return merge(toSortList(head, mid), toSortList(mid, tail));
}//调用的排序函数
struct ListNode* sortList(struct ListNode* head) {return toSortList(head, NULL);
}

时间复杂度：O(nlogn)，其中 n 是链表的长度。

空间复杂度O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

第四题

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val){if(head==NULL){return NULL;}struct ListNode *dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead->next=head;struct ListNode*cur=dummyHead;//利用哨兵位，避免传入空指针的情况，而对下一个数据进行检索的写法。while(cur->next!=NULL)//当遇到倒数第二个节点时 if else语句已经解决了尾数据是该删还是不该删{if(cur->next->val==val){cur->next=cur->next->next;//跳过该节点指向下下个节点}else{cur=cur->next;//直接接入下一个数据，若接入的是尾数据则跳出循环}}return dummyHead->next;
}

第五题

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* dummyHead=malloc( sizeof(struct ListNode) );struct ListNode*cur1=head;struct ListNode*cur2=NULL;//尾的next置为空while(cur1)//依次取下链表的数据连接在NULL上面{struct ListNode *tmp=cur1->next;cur1->next=cur2;cur2=cur1;cur1=tmp;}return cur2;
}