【leetcode刷题】T108-重排链表

示例 :
给定链表 ->->->, 重新排列为 ->->->3.
示例 :
给定链表 ->->->->, 重新排列为 ->->->->3.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return 
        # 链表分为前后两部分
        p = head
        q = head
        while q.next and q.next.next:
            p = p.next
            q = q.next.next

        # 后半部分的链表翻转
        head2 = p
        q = p.next
        r = p.next
        while q:
            r = q.next
            q.next = p
            p = q
            q = r

        head2.next = None
        head2 = p

        # 链表插入
        p = head
        q = head2
        while p and q:
            r = p.next
            p.next = q
            s = q.next
            q.next = r
            p = r
            q = s

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next)
            return;
        // 切成两个链表
        ListNode* p = head;
        ListNode* q = head;
        while(q->next && q->next->next){
            p = p->next;
            q = q->next->next;
        }
        ListNode* head2 = p;
        // 链表后半部分翻转
        q = p->next;
        ListNode* r = p->next;
        while(q){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        head2->next = NULL;
        head2 = p;

        //组成新链表
        p = head;
        q = head2;
        ListNode* s = NULL;
        while(p && q){
            r = p->next;
            p->next = q;
            s = q->next;
            q->next = r;
            p = r;
            q = s;
        }
    }
};