链表问题

1、给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
一定要考虑head节点是否为空，不然定义指针指向head->next会报错
示例：
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode *pre,*cur;
        if(!head || !head->next)
            return head;
        pre = head;
        cur = head->next;
        while(cur && cur->next){
            ListNode *tmp = pre->next;
            pre->next = cur->next;
            cur->next = cur->next->next;
            pre->next->next = tmp;

            pre = pre->next;
            cur = cur->next;
        }
        return head;
    }
};
2、删除链表中等于给定值 val 的所有节点。
考虑到第一个节点也可能被删除，所以要设置一个虚拟的头结点，令其指向head
 
示例：
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
 
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *cur;
        ListNode *h = new ListNode(-1);
        h->next = head;
        cur = h;
        while(cur->next){
            if(cur->next->val == val){
                cur->next = cur->next->next;
            }else{
                cur = cur->next;
            }
        }
        return h->next;
    }
};
3、Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
(交换相邻结点，一定要注意设置虚拟头结点) 
Example:
Given1->2->3->4, you should return the list as2->1->4->3.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)
            return head;
    
        ListNode *preHead = new ListNode(0);
        preHead->next = head;
        ListNode *p = preHead;
        while(p->next&&p->next->next){
            ListNode *node1 = p->next;
            ListNode *node2 = node1->next;
            ListNode *next = node2->next;
            node1->next = next;
            node2->next = node1;
            p->next = node2;
            p = node1;
        }
        return preHead->next;
    
    }
};
4、请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
示例：
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
【通过将待删除节点后面的值赋给待删除节点，然后将其后的节点删除】 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode *t = node->next;
        node->val = node->next->val;
        node->next = node->next->next;
        delete t;
    }
};
5、使用快慢指针找到链表的中心点，用栈进行存储

请判断一个链表是否为回文链表。

示例 1: 

输入: 1->2 输出: false

示例 2: 

输入: 1->2->2->1 输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        if(head==NULL||head->next==NULL)    //特殊处理
        return true;

        ListNode *fast=head;
        ListNode *slow=head;
        ListNode *left=head;
            stack<int>s;
            s.push(head->val);      //利用快慢指针法让slow找到中心点
        while(fast->next&&fast->next->next)
        {

            fast=fast->next->next;
            slow=slow->next;
            s.push(slow->val);
        }

        if(fast->next==NULL)        //奇数链做退栈处理，保证栈里面和slow的右边对称
            s.pop();
        while(!s.empty())
        {
            if(s.top()!=slow->next->val)
            {
                return false;
            }

            else
            {
                slow=slow->next;
                s.pop();
            }
        }
        return true;

    }
};