转载

reorder-list

reorder-list

Given a singly linked list LL 0→L 1→…→L n-1→L n,

reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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. 翻转中间节点后的链表部分

    翻转可以用栈实现,这是最简单的,但不是in place的方法

    可以参考 链表翻转blog

  3. 合并两部分链表

代码

/**
 * 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) return;
       ListNode *fast = head;
       ListNode *low = head;

       /*快慢指针找到中间节点*/
       while(fast != NULL && fast->next != NULL) {
           fast = fast->next->next;
           low = low->next;
       }

       if(low->next == NULL) return;

       ListNode* tempOne = head;
       ListNode *tempTwo = reverse(low->next);
       ListNode *temp = NULL;

       low->next = NULL;

       /*链表合并*/
       while(tempTwo != NULL){
           temp = tempTwo->next;
           tempTwo->next = tempOne->next;
           tempOne->next = tempTwo;
           tempOne = tempTwo->next;
           tempTwo = temp;
       }
    }

    /*链表翻转*/
    ListNode* reverse(ListNode* head) {
        ListNode *p, *q, *r;
        p = head;
        q = head->next;
        head->next = NULL;

        while(q != NULL){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        return p;
    }
};
正文到此结束
本文目录