首页 > 代码库 > LeetCode OJ 143. Reorder List(两种方法，快慢指针，堆栈)

LeetCode OJ 143. Reorder List(两种方法，快慢指针，堆栈)

2024-08-19 23:39:37   225人阅读

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}.

 

Subscribe to see which companies asked this question

解答：

第一种方法是利用快慢指针找到中间节点，然后反转后半部分链表后合并链表，当然这里要注意分类讨论奇数个节点和偶数个节点的情况，另外注意合并链表后新链表的结尾要赋值为NULL，否则主函数中遍历链表就是在遍历循环链表了……还有就是一如既往地要注意空表的情况……

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void reorderList(struct ListNode* head) {
    struct ListNode *fast = head, *slow = head, *tmp, *tmp_head = NULL, *tmp_tail;
    
    while(NULL != fast&&NULL != fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    if(NULL == fast){
        tmp_tail = slow;
    }
    else{
        tmp_tail = slow->next;
    }
    while(NULL != tmp_tail){
            tmp = tmp_tail->next;
            tmp_tail->next = tmp_head;
            tmp_head = tmp_tail;
            tmp_tail = tmp;
    }
    slow = tmp_head;
    if(NULL == fast){
        while(NULL != slow){
            tmp = slow->next;
            slow->next = head->next;
            if(NULL == tmp){
                slow->next = NULL;
            }
            head->next = slow;
            head = slow->next;
            slow = tmp;
        }
    }
    else{
        while(NULL != slow){
            tmp = slow->next;
            slow->next = head->next;
            head->next = slow;
            head = slow->next;
            slow = tmp;
        }
        head->next = NULL;
    }
}

第二种方法是利用堆栈FILO，这样的话顺序遍历链表将节点压入堆栈后，节点依次弹出链表的顺序就和题中要求的顺序吻合了，而且压入堆栈的过程中还得到了链表长度……这里需要注意的还有就是变量的值在操作中可能会更改，需要用临时变量来保存当前值…… 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void reorderList(struct ListNode* head) {
    struct ListNode* stack[100000];
    struct ListNode *tmp = head;
    int top = -1, size, tmp_val;
    
    while(NULL != tmp){
        stack[++top] = tmp;
        tmp = tmp->next;
    }
    size = (top + 1) / 2;
    tmp_val = top;
    while(size){
        size--;
        tmp = stack[top];
        top--;
        tmp->next = head->next;
        head->next = tmp;
        head = tmp->next;
    }
    if(0 == tmp_val % 2){
        head->next = NULL;
    }
    else if(NULL != tmp){
        tmp->next = NULL;
    }
}

 

LeetCode OJ 143. Reorder List(两种方法，快慢指针，堆栈)


联系
我们