题解 | #链表的奇偶重排#

链表的奇偶重排

http://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3

题意:

  • 输入一个单链表,将该单链表奇数节点放在前半部分,偶数节点放在后半部分,不改变奇数节点和偶数节点之间的相对顺序,返回新的链表。

方法一:

解题思路:

  • 一次遍历,奇数的节点组成一个链表,偶数的节点组成一个链表,然后将链表合并即可。
  • oddHead,oddTail记录奇数节点链表的头尾节点;evenHead,evenTail记录偶数节点链表的头尾节点;遍历时更新oddTail,evenTail;合并时将evenHead接在oddTail之后。

图解如下:

图片说明

代码如下:

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head==nullptr||head->next==nullptr)
            return head;
        //分别表示奇数位节点组成的链表头尾节点,以及偶数位节点组成的链表头尾节点。
        ListNode *oddHead=head,*evenHead=head->next;
        ListNode *oddTail=head,*evenTail=evenHead;
        //p是遍历的临时节点
        ListNode* p=head->next->next;
        while(true){
            //p不存在则退出循环
            if(!p)
                break;
            //奇数位节点
            oddTail->next=p;
            p=p->next;
            oddTail=oddTail->next;
            if(!p)
                break;
            //偶数位节点
            evenTail->next=p;
            p=p->next;
            evenTail=evenTail->next;
        }
        //连接两个链表
        oddTail->next=evenHead;
        evenTail->next=nullptr;
        return oddHead;
    }
};

复杂度分析:

时间复杂度:,遍历一次。
空间复杂度:,常数个临时变量。

全部评论

相关推荐

顺丰 开发岗 (n+1)×14
乐趣使然:犹豫一点都是对团子的不尊重😋
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务