leetcode 初级算法 链表

删除链表中的节点

题目：函数唯一的参数是要删除的节点的指针，且指向的节点绝对不是最后一个。
思路：自己一开始想不明白没有给头指针怎么操作，看了别人的思路才懂了，只需要移动就行了。
AC代码：

class Solution {
public:
    void deleteNode(ListNode* node) {
        //将node之后的每一个都往前
        ListNode* tail;
        while(node->next!=NULL)
        {
            tail = node;
            node->val = node->next->val;
            node = node->next;
        }
        tail->next = NULL;
        delete(node);
    }
};

删除链表的倒数第N个节点

AC代码:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       stack<ListNode*> p;
        ListNode* cur = head;
        while(cur!=NULL)
        {
            p.push(cur);
            cur = cur->next;
        }
        for(int i = 0;i<n;i++)
        {
            p.pop();
        }
        if(p.size()==0)
        {head = head->next;
            return head;}
        else{
        cur = p.top();
        cur->next = cur->next->next;
        return head;}
    }
};

反转链表

cuowudaima

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;    //这个链表只有一个节点，不需要reverse了
        else
        {
            //
            ListNode* p = head,*a;
            while(p->next!=NULL)
            {
                a=p;
                p=p->next;
            }
            a->next = NULL;
            p->next = head;
            head = p;
            reverseList(head->next);
            return head;
        }
    }
};

AC

public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;    //这个链表只有一个节点，不需要reverse了
        else
        {
            //
            ListNode* p = head,*a;
            while(p->next!=NULL)
            {
                a=p;
                p=p->next;
            }
            a->next = NULL;
            p->next = head;
            head = p;
            head->next=reverseList(head->next);
            return head;
        }
    }
};

合并两个有序链表

cuowudaima:

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

AC(recursion)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL&&l2==NULL) return NULL;
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        ListNode* temp;
        if(l1->val<l2->val)
        {
            temp = l1;
            l1=l1->next;
            temp->next = mergeTwoLists(l1,l2);
            return temp;
        }
        else
        {
            temp = l2;
            l2=l2->next;
            temp->next = mergeTwoLists(l1,l2);
            return temp;
        }
        return NULL;    //for passing compiling only 
    }
};

回文链表

yuanli:make use of a stack and a queue.
tongguodaima:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> back;
        queue<int> front;
        int cnt = 0;
        while(head!=NULL)
        {
            cnt++;
            back.push(head->val);
            front.push(head->val);
            head = head->next;
        }
        int x = cnt/2;     //if 6 items,then check 3 times.if 5 items,check 2 times
        while(x--)
        {
            int v = back.top();
            int u = front.front();
            if(v!=u) return false;
            back.pop();
            front.pop();
        }
        return true;
    }
};

huanxing链表

cuowu

class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> visited;
        while(head!=NULL)
        {
            if(visited.find(head)!=visited.end()) {return false;}
            visited.insert(head);
            head = head->next;
        }
        return true;
    }
};

bierende:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return false;
        if(head->next==head) return true;
        ListNode* t=head->next;
        head ->next = head;
        return hasCycle(t);
    }
};