Leetcode0143--Reorder List 链表重排

【转载请注明】

具体的图示可查看

---

 

代码一

 

/**
 * 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==NULL || head->next ==NULL) return;
        // two pointers split the list
        // 快慢指针，快指针到尾时，慢指针在前list尾部
        // example: 1->2->3->4->5 fast=5,slow=3, 1->2->3 & 4->5
        // example: 1->2->3->4    fast=3,slow=2, 1->2    & 3->4
        ListNode *slow = head, *fast = head;
        while(fast->next !=NULL && fast->next->next !=NULL){
            slow = slow ->next;
            fast = fast->next->next;
        }
        ListNode *head1 = head;
        // reverse the second list(with large numbers)
        // 翻转第二个链表
        ListNode *head2 = reverseList(slow->next);
        slow->next = NULL;
        while(head2!=NULL){             // list1 size >= list2 size
            ListNode *next1 = head1->next;
            ListNode *next2 = head2->next;
            head1->next = head2;
            head2->next = next1;
            head1 = next1;
            head2 = next2;
        }
        if(head1!=NULL){
            head1->next = NULL;
        }
    }
    // reverse list
    ListNode *reverseList(ListNode *head){
        if(head==NULL || head->next ==NULL) return head;
        ListNode * new_head = NULL;
        while(head!=NULL){
            ListNode *pNext = head->next;
            head->next = new_head;
            new_head = head;
            head = pNext;
        }
        return new_head;
    }
};

 

---

/**
 * 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) {
        stack<ListNode* > nodestack;
        int length=0;
        // 计算链表长度，结点压入stack
        ListNode *temp = head;
        while(temp){
            length++;
            nodestack.push(temp);
            temp = temp->next;
        }
        // 栈弹出，连接链表
        temp = head;
        int cnt = length/2;
        while(cnt){
            ListNode *head2 = nodestack.top();
            nodestack.pop();
            ListNode *headNext = temp->next;
            temp->next =head2;
            head2->next = headNext;
            temp = headNext;
            cnt--;
        }
        // 总数为odd，temp指向末尾元素
        // 总数为even，temp会和前元素重复，此处删除
        if(length%2){
            temp->next = NULL;
        }else{
            temp = NULL;
        }
    }
};