LeetCode个人题解（剑指offer 21-25）21. 调整数组顺序使奇数位于偶数前面，22. 链表中倒数第k个节点，24. 反转链表，25. 合并两个排序的链表

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题解：交换

有点采用快速排序的思想。思路很简单，从左向右，直到遇到一个偶数，从右向左，直到遇到一个奇数，两者交换即可

代码：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        while(left<right){
            while(left<right&&nums[left]%2==1) ++left;
            while(left<right&&nums[right]%2==0) --right;
            swap(nums[left],nums[right]);       
        }
        return nums;
    }
};

结果：

剑指 Offer 22. 链表中倒数第k个节点

题解：

我们都知道链表是不能随机存储的，我们想要知道倒数第k个点是多少，就需要遍历一遍链表，把链表的长度length记下来，第二遍遍历到length-k处。但是这样时间复杂度接近O（n^2)。能不能一遍就能找到？

首先，定义两个指针，一左一右，让right先走k-1个节点，left在头节点处。

然后，right一直走到链表末尾，left便走到了倒数第k个节点处，返回left即可。

代码：

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *left,*right;
        left=right=head;
        while(--k)
            right=right->next;
        
        while(right->next){
            right=right->next;
            left=left->next;
        }
        return left;
    }
};

结果：

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

题解：

方法一：头插法

首先，排除链表为空或者只有一个数的情况。

将尾指针r走到链表最后一个节点处，pre和p两个指针从头节点开始遍历，p是pre的后继节点。

每走一个节点，便将该节点用头插法的方式插入到尾指针r后面。

该算法要遍历两次，所以时间复杂度为O(n^2)。

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode *r,*pre,*p;
        pre=r=head;
        p=head->next;
        while(r->next)
            r=r->next; 
        while(pre!=r){
            pre->next=r->next;
            r->next=pre;
            pre=p;
            p=p->next;
        }
        return r;
    }
};

结果：

 方法二：

首先，排除链表为空或者只有一个数的情况。

将头节点断开，指针p遍历链表，每经过一个节点，先把它后继节点暂存，然后把它放到头节点的前面，头节点变成该节点，p变成后继节点，依次循环

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode *h,*temp,*p;
        h=head;
        p=head->next;
        h->next=nullptr;
        while(p){
            temp=p->next;
            p->next=head;
            head=p;
            p=temp;
        }
        return head;
    }
};

结果：

剑指 Offer 25. 合并两个排序的链表

 

题解：

首先，排除链表为空的情况。

从两个表中确定头节点。

依次比较两个链表的节点大小，将小的那个添加到新表。

最后判断两个表是否都已经走完。

返回新表头节点。

代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        ListNode *head,*p;
        if(l1->val<l2->val){
            head=l1;
            l1=l1->next;
        }
        else{
            head=l2;
            l2=l2->next;
        }
        p=head;
        while(l1!=nullptr&&l2!=nullptr){
            if(l1->val<l2->val){
                p->next=l1;
                l1=l1->next;
            }
            else{
                p->next=l2;
                l2=l2->next;
            }
            p=p->next;
        }
        if(l1!=nullptr) p->next=l1;
        if(l2!=nullptr) p->next=l2;
        return head;
    }
};

 

结果：