【leetcode】328 Odd Even Linked Lis

发表于 | 分类于 ，

链表按奇偶索引重排


描述

给定一个链表，需要对链表重新排序，将所有奇数索引节点放在前面，偶数索引节点放在后面，按照要求，第一个节点之后连接的应该是第三个节点，之后是第五个节点，连完所有的奇数索引节点后，再将第二个节点放到奇数节点后，当然，第四个节点是连在第二个节点后面的。

样例

样例1

1
2
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

样例2

1
2
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

思路

最简单的思路，遍历节点，轮换添加到奇数索引节点、偶数索引节点的后面，最后进行连接。

遇到的问题：

  1. 未将最后一个节点的 next 变为 NULL 造成死循环
  2. 访问 NULL -> next
  3. 将 head->next 作为偶数索引的头节点，实际上 head ->next 会因为奇数节点的增加而改变，应该设置另一个变量保存。

第二种思路：设置一个 pOdd 节点代表奇数序列节点的尾节点，设置一个偶数序列的尾节点 oEven, 每次将偶数的尾节点的后一个节点添加到奇数的尾节点上。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
private:

public:
    ListNode * oddEvenList(ListNode* head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL) {
            return head;
        }
        ListNode * tailA = head;
        ListNode * tailB = head->next;
        ListNode * h2 = head->next;
        ListNode * next = tailB->next;
        int fg = 1;
        while (next) {
            if (fg == 1) {
                tailA->next = next;
                tailA = tailA->next;
                fg = 2;
            }
            else if (fg == 2) {
                tailB->next = next;
                tailB = tailB->next;
                fg = 1;
            }
            next = next->next;
        }
        tailA->next = h2;
        tailB->next = NULL;
        return head;
    }
};

将题目变一下，按节点的值的奇偶重排：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:

public:
	ListNode * oddEvenList(ListNode* head) {
		if (head == NULL) { return NULL; }
		else if (head ->next == NULL) { return head; }
		ListNode *q = head->next;
		int odd = head->val & 1;

		auto prev = head;
		while ( q && (head->val + q->val) % 2 ==0 ) {
			prev = q;
			q = q->next;
		}
		if (q == NULL) {
			return head;
		}

		ListNode * ptail = prev;
		ListNode * qtail = q;

		ListNode *next = q->next;

		while (next) {
			if ((next->val & 1 )== odd) {
				ptail->next = next;
				ptail = next;
				//ptail->next = NULL;
			}
			else {
				qtail->next = next;
				qtail = next;
				//qtail->next = NULL;
			}
			next = next->next;
		}
		ptail->next = q;
		qtail ->next= NULL;
		return head;
	}
 };

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        ListNode* pOdd = head;
        ListNode* p = head->next;
        ListNode* pNext = NULL;
        while(p && (pNext=p->next)) {

            p->next = pNext->next;
            pNext->next = pOdd->next;
            pOdd->next = pNext;

            p = p->next;
            pOdd = pOdd->next;

        }
        return head;
    }
};

参考

原题链接
参考链接