1. 反转链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路：翻转链表使用头插法

ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* newHead = head;
        head = head->next;
        newHead->next = nullptr;
        ListNode* ptr = nullptr;
        while(head != nullptr)
        {
            ptr = head;
            head = head->next;
            ptr->next = newHead;
            newHead = ptr;
        }
        return newHead;
    }

---

2. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：每次两个链表的头进行比较，小的插入到新链表的后面，如果两个链表中的某一个链表已经遍历完，则观察另一个链表是否有剩余项，如果有，全部接入到新链表的后面。有两种特殊情况值得注意：
1.其中一个链表为空链表
2.两个全部为空链表。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(nullptr == l1 && nullptr == l2)
            return nullptr;
        if (nullptr != l1 && nullptr == l2)
            return l1;
        if (nullptr != l2 && nullptr == l1)
            return l2;
        ListNode* newHead(nullptr);
        if(l1->val <= l2-> val)
        {
            newHead = l1;
            l1 = l1->next;
        }
        else
        {
            newHead = l2;
            l2  = l2->next;
        }
        ListNode* end = newHead;
        while(l1!=nullptr&&l2!=nullptr)
        {
            if( l1->val <= l2->val)
            {
                end->next = l1;
                l1 = l1->next;
            }
            else
            {
                end->next = l2;
                l2 = l2->next;
            }
            end = end->next;
        }
        if(l1 != nullptr)
        {
            end->next = l1;    
        }
        else if( l2 != nullptr )
        {
            end->next = l2;
        }
        else
        {
            end->next = nullptr;
        }
        return newHead;
    }
};

---

3. 回文链表

请判断一个链表是否为回文链表。
例：
输入: 1->2->2->1
输出: true
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：首先遍历一遍链表获取链表个数，然后再遍历一半链表，并且利用头插法进行逆序操作，然后会得到两个子链表，如果子链表全部相等，则证明是回文链表。没有额外的空间开销，并且时间复杂度是n+n/2 = o(n)

bool isPalindrome(ListNode* head) {
    if ( nullptr == head || nullptr == head->next )
        return false;
    ListNode* ptr = head;
    int size = 0;
    while(nullptr != ptr )
    {
        ptr = ptr->next;
        ++size;
    }
    ListNode* halfHead = head;
    head = head->next;
    halfHead->next = nullptr;
    for(int i= 1 ;i< size/2;i++)
    {
        ptr = head;
        head = head->next;
        ptr->next = halfHead;
        halfHead = ptr;
    }
    if( size%2 != 0)
        head = head->next;
    for(int i = 0 ;i < size/2 ; i++)
    {
        if(head->val != halfHead->val)
            return false;
        head = head->next;
        halfHead = halfHead->next;
    }
    return true;
}

---

4. 环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

解题思路：快慢针，没有什么可说的，简单的跟冒泡排序一样。

 bool hasCycle(ListNode *head) {
        if( nullptr == head || nullptr == head->next )
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while( fast != slow ){
            if( nullptr == fast || nullptr == fast->next )
                return false;
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }