leetcode

0 class Solution {

1 ListNode *reverseList(ListNode *head) {

2 ListNode *p, *q, *r;

3

4 p = head, q = nullptr;

5 while (p) {

6 r = q;

7 q = p;

8 p = p->next;

9 q->next = r;

10 }

11

12 return q;

13 }

14

15 ListNode *bmiddleNode(ListNode *head) {

16 ListNode *fast, *slow;

17 fast = slow = head;

18 while (fast->next && fast->next->next) {

19 fast = fast->next->next;

20 slow = slow->next;

21 }

22

23 return slow;

24 }

25

26 public:

27 void reorderList(ListNode *head) {

28 ListNode *bmid = bmiddleNode(head);

29 ListNode *rev = reverseList(bmid->next);

30 bmid->next = nullptr;

31

32 ListNode top, *tmp = &top, *a, *b, *an;

33 for (a = head, b = rev; b; b = b->next, a = an) {

34 an = a->next;

35 tmp = tmp->next = a;

36 tmp = tmp->next = b;

37 }

38 if (a) tmp = tmp->next = a;

39 tmp->next = nullptr;

40 }

41 };