[数据结构与算法]链表相关题目

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题

有环链表的环入口地址计算

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

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

链表相交判断

通过对齐两链表的尾部，再对两链表逐一进行判断

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA;
        ListNode *curB = headB;

        int lenA = 0;
        int lenB = 0;
        while(curA != NULL){
            lenA++;
            curA=curA->next;
        }
        while(curB != NULL){
            lenB++;
            curB=curB->next;
        }

        curA=headA;
        curB=headB;
        int t;

        if(lenA > lenB){
            t=lenA-lenB;
            while(t--){
                curA=curA->next;
            }
        }
        else if(lenA < lenB){
            t=lenB-lenA;
            while(t--){
                curB=curB->next;
            }
        }

        while(curA != NULL){
            if(curA == curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return NULL;

    }
};

删除链表的第N个节点

注意让快指针走n+1个结点，且使用虚拟头结点，方便对源头结点的删除，结束条件为fast等于null指针

重点是使用虚拟头结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *newhead = new ListNode(0, head);
        ListNode *slow = newhead;
        ListNode *fast = newhead;
        while(fast != nullptr && n--){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast != nullptr){
            fast=fast->next;
            slow=slow->next;

        }

        ListNode *del = slow->next;
        slow->next=slow->next->next;
        delete del;
        return newhead->next;    
    }
};

两两交换链表中的节点

使用虚拟头结点方便对头结点的操作

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *newhead = new ListNode(0);
        ListNode *cur=newhead;
        cur->next = head;
        while(cur->next != nullptr && cur->next->next != nullptr){
        
			//记录结点
            ListNode *temp1 = cur->next;
            ListNode *temp2 = cur->next->next->next;
			
			//交换过程
            cur->next=temp1->next;
            cur->next->next = temp1;
            temp1->next=temp2;
			
			//下一次交换的准备
            cur=temp1;
        }
        return newhead->next;
    }
};

翻转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre, *cur, *temp;
        pre = nullptr;
        cur=head;
        while(cur != nullptr){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};

移除链表元素

使用虚拟头结点，方便对头结点的操作

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        
        ListNode* newhead = new ListNode(0);    //虚拟头结点
        newhead->next = head;
        
        //开始遍历
        ListNode* cur = newhead;
        while(cur->next != nullptr){
            if(cur->next->val == val){             //找到目标结点
                ListNode *del = cur->next;
                cur->next = del->next;
                delete del;
            }
            else{
                cur=cur->next;
            }
            
        }
        return newhead->next;
    }
};