链表的奇偶重排
思路一
- 首先需要明确，题目所说的奇偶是节点编号的奇偶，而不是节点数据的奇偶。
- 既然如此，我们就可以把链表编号为奇数的节点一起放入一个新建链表，将编号为偶数的节点一起放入另一个新建链表，最后再将连个链表合并即可。
具体步骤
- 首先定义两个链表头odd，even分别存放编号为奇数、偶素的节点。
- 再定义三个指针变量cur1，cur2，cur3使其分别指向原链表的头，odd的头，even的头，定义count并初始化为1，代表节点编号
- 对原链表进行遍历，当count为奇数，则将cur1所代表的节点放入odd，否则放入even。每放入一个节点，都令count加1，cur1下滑一个节点，直到cur1为空，即走到表尾。
- 最后，将even接到odd后面，再返回odd即可。
实现代码
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ struct ListNode* oddEvenList(struct ListNode* head ) { struct ListNode *odd = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *even = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *cur1 = head, *cur2 = odd, *cur3 = even; int count = 1; while(cur1) { if(count % 2) { cur2->next = cur1; cur2 = cur1; } else { cur3->next = cur1; cur3 = cur1; } cur1 = cur1->next; count++; } cur2->next = even->next; //odd和even的头结点都没有存入具体的数据，因此需要舍去 cur3->next = NULL; //令表尾为空 return odd->next; //返回第一个有效节点 }
思路二
- 我们可以简单得到，链表第一个节点为奇，第二个为偶，第三个为奇，第四个为偶········
- 那么，我们就可以定义两个指针变量odd，even使其分别指向第一个奇节点，第一个偶节点
- 断开odd与even的连接，使odd指向even的下一个节点（即下一个奇节点），令odd为下一个奇节点，接着，令even指向odd的下一个节点（即下一个偶节点），并令even为下一个偶节点。
- 重复第三步，直到even或even的下一个节点为空，这样我们就将所有的奇节点连接到一起，所有的偶节点连接到一起了。
- 但是，怎么将他们链接成一个链表呢？我们好像找不到所有偶节点的头，因此，我们可以在最开始定义一个指针evenhead来代表偶节点的头，并使其为第一个偶节点，这样不就可以成功链接了吗。
- 如图：
具体步骤
- 首先对链表进行判断，当链表为空，只有一个或两个节点时，不需要进行奇偶重排，直接返回头结点
- 定义两个指针变量odd，even，使其分别指向第一个奇节点，第一个偶节点
- 定义evenhead，保存第一个偶节点
- 断开odd与even的连接，使odd指向even的下一个节点（即下一个奇节点），令odd为下一个奇节点，接着，令even指向odd的下一个节点（即下一个偶节点），并令even为下一个偶节点，直到even或even的下一个节点为空。
- 令odd指向evenhead完成链接
- 返回head
实现代码
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ struct ListNode* oddEvenList(struct ListNode* head ) { if(head == NULL || head->next == NULL || head->next->next == NULL) return head; struct ListNode *odd = head ,*even = head->next, *evenhead = head->next; while(even && even->next) { //odd连接even的后一个，即奇数位 odd->next = even->next; //odd进入后一个奇数位 odd = odd->next; //even连接后一个奇数的后一位，即偶数位 even->next = odd->next; //even进入后一个偶数位 even = even->next; } //even整体接在odd后面 odd->next = evenhead; return head; }
