算法面试3-链表

算法3 链表

链表

例题：206 Reverse Linked List
反转一个链表

struct ListNode{
    int val;
    ListNode *next;
    ListNode (int x):val(x),next(NULL){}

};
class Solution{
public:
    ListNode*reverselist(ListNode *head)
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur!=NULL){
            ListNode*next = cur->next;
            cur->next = pre; //链表指向反转，指向前面的pre
            //链表后移 pre 变成cur cur编程next
            pre = cur;
            cur = next;
        }
        return pre;
}

例题：83
例题：328

例题：2 Add Two Numbers

设立链表的虚拟头结点

例题：203 Remove Linked List Elements

class Solution{
public:
    ListNode*removeElements(ListNode *head,int val){
        while(head != NULL&&head->val == val){
            ListNode *delNode = head;
            head = delNode->next
        }
        if(head ==NULL)
            return NULL;
        ListNode * cur = head;
        while(cur->next != NULL){
            if(cur->next->val == val){
                //删除cur->next
                ListNode *delNode = cur->next; //给要删除的节点存储一下
                cur->next = delNode->next;
                delete delNode;
                //delnode->next = NULL;
            }
            else
                cur = cur->next;
        }       
        return head;
}
};

这里采用虚拟头节点的方法来简化代码
在head前创建一个dummyhead

class Solution{
public:
    ListNode*removeElements(ListNode *head,int val){
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode * cur = dummyHead;
        while(cur->next != NULL){
            if(cur->next->val == val){
                //删除cur->next
                ListNode *delNode = cur->next; //给要删除的节点存储一下
                cur->next = delNode->next;
                delete delNode;
                //delnode->next = NULL;
            }
            else
                cur = cur->next;
        }       
        ListNode *retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
        }
};

例题：24 Swap Nodes in pairs

leetcode 已完成

例题： 148 sort list

例题： 237 Delete node in a linked list
删除某一个指定的节点

class Solution{
public:
    void deleteNode(ListNode * node){
        if(node == NULL)
            return;
        if(node->next == NULL){
            delete node;
            node = NULL; //这里node在最后，他的前一个节点指向NULL
            return;

        }
        node->val = node->next->val;
        ListNode *delnode = node->next;
        node->next = delNode->next; //跳过这个节点指向下一个节点
        delete delnode;
        return;
    }
};

双指针技术

例题： 19 remove Nth Node from end of list
如1->2->3->4->5->NULL,n=2
返回1->2->3->5
n是从0开始还是从1开始
n不合法怎么办？
解法1：先遍历一边计算链表长度；再遍历一边删除倒数第n个节点
能不能只遍历一边链表？

class Solution{
public:
    ListNode *removeNthFromEnd(ListNode *head,int n){
        assert(n>=0);
        ListNode *dummyHead = new ListNode(0);
        dummyHead ->next = head;
        ListNode *p = dummyHead;
        ListNode *q = dummyHead;
        for(int i = 0;i<n+1;i++){
            assert(q);
            q = q->next;//q向后移动到正数第n个位置，使得pq位置长度为n
        }
        while(q!=NULL){
            p = p->next;
            q = q->next; //滑动双索引
            ListNode *delNode = p->next;//删除p后面的节点
            p->next = delNode->next;
            delete delNode;
            ListNode *retNode = dummyHead->next;
            delete dummyHead;
            return retNode;
        }
    }

例题61 rotate list
例题143 Reorder List
链表无法随机访问数据，如何获得中间的元素
两次遍历？一次遍历？
例题: 234 palindrome linked list
能否使用O(1)的空间复杂度解决问题？