链表常用操作整理

最近在复习链表的常用操作，顺便整理到博客中方便以后复习。
1.链表定义
对于单向链表来说，包括数据域和指针域，数据域：用于存储数据元素的数值，指针域：指向下一个节点位置。

struct Node {
    int value;
    Node * next;
};

2.常用操作
链表常用操作处理过程中，很重要个一个注意点是在操作过程中不要把链表给处理断了，即找不到next位置。
2.1 插入节点
在链表中的某一个节点p后面插入一个新的节点

//p节点后插入值为i的节点
void insertNode(Node *p, int i) {
    Node* node = new Node;
    node->value = i;
    node->next = p->next;
    p->next = node;
}

2.2 在头节点后插入节点

void insertHeadList(Node *head, int i) {
    Node *node = new Node;
    node->data = i;
    node->next = head;
    head = node;
    printf("insertHeadList函数执行，向表头插入元素成功\n");
}

2.3 删除节点
当需要删除一个节点p时，只需要将p的前一个节点的next赋为p->next,但是由于是单向的，只知道p，无法知道p前一个节点，所以需要转换思路。将p下一个的节点覆盖到p节点即可，这样就等效于将p删除了。

void deleteNode(Node *p) {
    p->value = p->next->value;
    p->next = p->next->next;
}

2.4 删除链表中所有与给定的数值相等的节点
具体分析见LeetCode 203. Remove Linked List Elements
代码实现：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == NULL)
            return head;
        ListNode* temp = head;
        while(temp->next != NULL) {
            if(temp->next->val == val)
                temp->next = temp->next->next; 
            else
                temp = temp->next;
        }
        return head->val == val ? head->next:head;
    }
};

2.5 翻转链表
a.非递归方式
将链表翻转，本来是1->2->3->4，翻转之后变为4->3->2->1，具体分析见
带有头节点的链表翻转

//单链表的转置,循环方法
Node* reverseByLoop(Node *head) {
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

b.递归方式
对于非递归方式，处理时从链表头到链表尾部，依次处理。而对于递归方式，则是找到末尾节点，从尾到头挨个处理。

//递归的方式进行链表翻转
Node* reverseByRecursion(Node *head) {
    if(head == NULL || head->next == NULL)
        return head;
    Node* new_list = reverseByRecursion(head->next);
    head->next->next = head;
    head->next = NULL;
    return new_list;
}

2.6 找出链表的中间节点
用slow和fast指针标记，slow每次走一步，fast每次走两步，当fast到尾节点时，slow就相当于总长度的一半，即在中间节点。

//找出中间节点
Node* findMidNode(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast->next != NULL && fast->next->next!=NULL) {
        slow = slow->next;
        //每次走一步
        fast = fast->next->next;
        //每次走两步
    }
    return slow;
}

2.7 找出倒数第k个节点
用slow和fast指针标记,fast指针先走k步，然后slow和fast同时走，当fast到达末节点时，slow在fast的前k个节点，即为倒数第k个节点。

//找出倒数第k个节点
Node* findKNode(Node* head,int k) {
    Node *slow = head;
    Node *fast = head;
    while (k-->0) {
        if(fast == NULL) {
            return NULL;
        }
        fast =fast->next;
    }
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

2.8 删除倒数第K个节点
具体分析见LeetCode 19. Remove Nth Node From End of List
代码实现：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(n-- > 0) {
            fast = fast ->next;
        }
        if(!fast)
            return head->next;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

2.9 合并两个有序的单链表
具体分析见LeetCode题目 LeetCode 21. Merge Two Sorted Lists

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(-1);
        ListNode *temp = head;
        while(l1 != NULL && l2 != NULL) {
            if(l1->val < l2->val) {
                temp->next = l1;
                l1 = l1->next;
            } else {
                temp->next = l2;
                l2 = l2->next;
            }
            temp = temp->next;
        }
        if(l1 != NULL)
             temp->next = l1;
        if(l2 != NULL)
            temp->next = l2;
        return head->next;
    }
};

2.10 判断链表是否有环
设置两个指针slow和fast，slow每次走一步，fast每次走两步。如果slow和fast相遇则存在环。
具体分析见LeetCode 141. Linked List Cycle

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
             return false;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

2.11 找到链表环的入口点
具体分析以及代码见 LeetCode 142. Linked List Cycle II
2.12 判断两个链表是否相交，并且求相交点
具体分析以及代码见 LeetCode 160. Intersection of Two Linked Lists