4/3日题解-剑指offer

1.调整数组顺序使奇数位于偶数前面
思路：维护两个指针，第一个指针指向第一个数字，从前向后，第二个指针指向数组的最后一个数字，从后往前。如果第一个指针指向的是偶数，第二个指针指向的是奇数，那么就交换这两个数字。终止条件是，第一个指针和第二个指针相遇。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.size()<2) return;
        int i=0,j=array.size()-1;
        while(i<j)
        {
            while(i<j&&!isEven(array[i]))
                i++;//定位第一个偶数
            while(i<j&&isEven(array[j]))
                j--;//定位第一个奇数
            if(i<j)
            {
                int temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }
    }
    bool isEven(int n)
    {
        return(n&1)==0;
    }
};

如果顺序不可以改变呢？

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int len=array.size();
        for(int i=0;i<len;i++)
        {
            for(int j=len-1;j>i;j--)
            {
                if(array[j]%2==1&&array[j-1]%2==0)
                {
                    swap(array[j-1],array[j]);
                }
            }
        }
        /*新建一个数组
        vector<int> result;
        int num=array.size();
        for(int i=0;i<num;i++)
        {
            if(array[i]%2==1)
                result.push_back(array[i]);
        }
        for(int j=0;j<num;j++)
        {
            if(array[j]%2==0)
                result.push_back(array[j]);
        }
        array=result;*/
    }
};

2.链表的倒数第k个节点
思路：维护两个指针，第一个指针从头结点开始先向前走k-1步，然后从第k步开始，第二个指针也开始从链表的头指针开始遍历，当第一个指针走到尾结点时，第二个指针到达倒数第k个节点。（注意鲁棒性，链表可能为空，k可能为0，可能不存在倒数第k个节点）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==nullptr||k==0) return nullptr;//特殊情况一·
        ListNode* p1=pListHead;
        ListNode* p2=nullptr;
        for(int i=0;i<k-1;i++)
        {
            if(p1->next!=nullptr)
                p1=p1->next;
            else
                return nullptr;//特殊情况二
        }
        p2=pListHead;
        while(p1->next!=nullptr)
        {
            p2=p2->next;
            p1=p1->next;
        }
        return p2;
    }
};

3.链表中环的入口节点
思路：如何判断有环？定义快慢指针，快指针一次走两步，慢指针一次走一步，如果快的追上了慢的，那么代表有环。如何找到环的入口？如果链表的环上面有n个节点，维护两个指针，第一个先走n步，然后第二个节点开始走，二者相遇的节点即为环的入口节点。如何找环上有几个节点？快慢指针相遇一定是在环中，从相遇节点出发，当再次回到这个节点时，可以得到环中节点的个数。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* MeetingNode(ListNode* pHead)
    {
        if(pHead==nullptr)
            return nullptr;
        ListNode* pSlow=pHead->next;
        if(pSlow==nullptr)
            return nullptr;//只有一个或没有节点
        ListNode* pFast=pSlow->next;
        while(pFast!=nullptr&&pSlow!=nullptr)
        {
            if(pFast==pSlow)
                return pFast;
            pSlow=pSlow->next;
            pFast=pFast->next;
            if(pFast!=nullptr)
                pFast=pFast->next;
        }//注意不要走到空指针
        return nullptr;
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* meetingNode=MeetingNode(pHead);
        if(meetingNode==nullptr)
            return nullptr;
        int nodeInLoop=1;
        ListNode* p1=meetingNode;
        while(p1->next!=meetingNode)
        {
            p1=p1->next;
            nodeInLoop++;
        }
        p1=pHead;
        for(int i=0;i<nodeInLoop;i++)
        {
            p1=p1->next;//先走环的数量步
        }
        ListNode* p2=pHead;
        while(p1!=p2)
        {
            p1=p1->next;
            p2=p2->next;
        }
    }
};

方法二：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    //设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点
    //(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *fast=pHead;
        ListNode *low=pHead;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            low=low->next;
            if(fast==low)
                break;
        }
        if(fast==NULL||fast->next==NULL) return NULL;
        low=pHead;
        while(low!=fast)//用while更好
        {
            fast=fast->next;
            low=low->next;         
        }
        return low;
    }
};

4.反转链表
思路：维护三个指针，分别指向当前遍历的节点，他的前一个和后一个节点。注意翻转后链表的头结点即原链表的尾结点。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr) return pHead;
        ListNode *pReversedHead=nullptr;//用于记录最后一个节点
        ListNode *pNode=pHead;//当前节点
        ListNode *pPrev=nullptr;//当前节点的前一个节点
        while(pNode!=nullptr)
        {
            ListNode* pNext=pNode->next;
            if(pNext==nullptr)
                pReversedHead=pNode;//如果pNode到达尾结点，令此节点等于pNode
            pNode->next=pPrev;
            pPrev=pNode;
            pNode=pNext;           
        }
        return pReversedHead;
    }
};

方法二：利用堆栈

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //利用堆栈
        if(pHead==NULL||pHead->next==NULL) return pHead;//一个结点或没有，直接返回
        stack<ListNode*> rev;
        ListNode *p=pHead;
        while(p->next)//把最后一个结点留下
        {
            rev.push(p);
            p=p->next;
        }
        ListNode *head=p;//新的头结点等于原链表的最后一个结点
        while(!rev.empty())//尾插法
        {
            p->next=rev.top();
            p=p->next;
            rev.pop();     
        }
        p->next=NULL;//最后一个结点指向NULL
        return head;       
    }
};