链表

title: 链表

2、环形链表

快慢指针，快指针一次走两步，慢指针一次走一步。单链表有环的话，快慢指针会相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if(NULL == head){
        return false;
    }

    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(slow!=NULL && fast!=NULL && fast->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

有关环的一系列问题，参考https://www.cnblogs.com/kira2will/p/4109985.html

5、反转链表

（1）迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(NULL==head || NULL==head->next){
        return head;
    }
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    struct ListNode* nex = NULL;
    while(cur != NULL)
    {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    return pre;
}

（2）递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(NULL==head || NULL==head->next){
        return head;
    }
    
    struct ListNode* ret = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return ret;
}

8、奇偶链表

我的思路是把奇数节点和偶数节点分别放一个链表，然后拼接

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* oddEvenList(struct ListNode* head){    
    if(NULL == head) {
        return NULL;
    }
    struct ListNode* odd = head;
    struct ListNode* evenHead = head->next;
    struct ListNode* even = evenHead;
   
    while(even!=NULL && even->next!=NULL)
    {
        odd->next = odd->next->next;
        odd = odd->next;
        even->next = even->next->next;
        even = even->next;
    }
    odd->next = evenHead;
    return head;
}

反映问题：链表需要进一步理解