重排链表

重排链表

http://www.nowcoder.com/questionTerminal/3d281dc0b3704347846a110bf561ef6b

🤯好难

不过没关系,还是刚出来了

其实方法是不难想到的,但是实现起来却比较麻烦,其中涉及有:

  1. 快慢指针(注意循环条件);
  2. 链表反转(熟练运用中间变量);
  3. 链表合并(哑节点很香)

嘻嘻,就4这样de^^

//
// Created by jt on 2020/8/8.
//
#include 
using namespace std;
/**
 * 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 || !head->next->next) return;
        // 1\. 用快慢指针找中间节点
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 2\. 对slow后面的部分逆序
        fast = slow->next;
        slow->next = nullptr;
        slow = nullptr;
        while (fast) {
            ListNode *temp = fast->next;
            fast->next = slow;
            slow = fast;
            fast = temp;
        }
        // 3\. 重新合并链表
        ListNode dummy(0);                   // 哑节点
        ListNode *r = &dummy;
        ListNode *p, *q;                     // 记录第一个节点
        while (slow && head) {
            p = head;
            q = slow;
            slow = slow->next;
            head = head->next;
            r->next = p;
            r = p;
            r->next = q;
            r = q;
        }
        if(slow) r->next = slow;
        if(head) r->next = head;
        head = dummy.next;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论

相关推荐

一颗宏心:华为HR晚上过了十二点后还给我法消息。
点赞 评论 收藏
分享
有工作后先养猫:太好了,是超时空战警,我们有救了😋
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务