Reorder List and Sum of Left Leaves

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

这个题目有点类似于综合题的感觉。对比给出实例。可以看出是将后半部的链表翻转后再与前半部合并。 算法分析： 1. 首先要分解链表，将链表一分为二。 2. 将后半部分链表倒序。 3. 合并两个链表。

class Solution { public: void reoderList(ListNode* head){ if(head == NULL) return ; ListNode* p1 = head; ListNode* p2 = splitList(head); p2 = reverseList(p2); mergelist(p1,p2); } ListNode* splitList(ListNode* head){ ListNode* slow = new ListNode(0); slow->next = head; ListNode* fast = slow; while(fast->next && fast->next->next){ slow = slow->next; fast = fast->next->next; } if(fast->next){ slow = slow->next; fast = fast->next; } ListNode* tmp = slow->next; slow->next =NULL; return tmp; } ListNode* reverseList(ListNode* head){ if(head == NULL) return head; ListNode* p=head; p = head->next; head->next = NULL; while(p){ ListNode* tmp = p->next; p->next = head; head = p; p = tmp; } return head; } void mergelist(ListNode* p1,ListNode* p2){ while(p2){ ListNode* tmp = p2; p2 = p2->next; p1->next =p2; tmp->next = p1->next; p1 = p1->next->next; } } };

再来看看二叉树：Sum of Left Leaves 计算所有左子树之和。 这个很容易理解，进行递归求解：

int sumOfLeftLeaves(ListNode* root){ if(root == NULL) return 0; if(root->left =NULL && root->left->left =NULL && root->left->right == NULL){ return root->val + sumOfLeftLeaves(root->right); } return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); }

好了，今天的解析到此为止了。