链表总结 | Wei Jiang

参考WalkingInTheWind的博客

Let’s Start //从最简单的开始

链表声明

struct ListNode
{
    int val;
    ListNode* next;
}

Index

求单链表中结点的个数
将单链表反转
查找单链表中的倒数第K个结点（k > 0）
查找单链表的中间结点
从尾到头打印单链表
已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
判断一个单链表中是否有环
判断两个单链表是否相交
求两个单链表相交的第一个节点
已知一个单链表中存在环，求进入环中的第一个节点
给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted

1. 求单链表中结点的个数

遍历整个链表就好, O(n)

int GetListLen(ListNode* head)
{
	int n = 0;
	if(head == NULL){
	    return 0;
    }
    ListNode* p = head;
    while(p != NULL){
    	p = p->next;
    	n++;
    }
    return n;
}

2. 将单链表反转

方法1
用3个指针实现反转，in-place，时间复杂度为O(n), 空间O(1)。
定义p, q, r指针，p = head, q = head->next, r = q->next;

p指向null，旧链表的头为新链表的尾；
q指向p(新链表的尾)
p = q, q = r; 然后下一轮循环(r=q->next)，参考代码如下：

ListNode* ReverseList(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || head->next == NULL){
	    return head;
    }
    ListNode* p = head;
    ListNode* q = head->next;
    head->next = NULL;
    while(q){
    	ListNode* r = q->next; //当前节点的下一届点；
    	q->next = p; //当前节点指向头(新链表的尾)
    	p = q; // p向前移动一位，到当前节点
    	q = r; // q想前移动一位，在一下循环处理下一个节点；
    }
    head = p; //循环结束，p == NULL, p指向head，实现反转
    return head;
}

方法2
从图上观察，方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

ListNode* ReverseList(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || head->next == NULL){
	    return head;
    }
    ListNode* p;
    ListNode* q;
    p = head->next
    while(p->next != NULL){
    	q = p->next;
    	p->next = q->next;
    	q->next = head->next;
    	head->next = p;
    }
    
    p->next = head; //like a loop
    head = p->next->next; // new head is old head->next
    p->next->next = NULL; // break the loop
    return head
}

3. 查找单链表中的倒数第K个结点（k > 0）

最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时的情况。时间复杂度为O（n）。也可以用双指针法，一个runner，一个chaser

ListNode* getkthNode(ListNode* head)
{
	// remember always test if node is NULL;
	if(head == NULL || k == 0){
	    return NULL;
    }
    ListNode* runner = head;
    ListNode* chaser = head;
    
    while(k > 1 && runner != NULL){
    	runner = runner->next;
    	k--;
    }
    
    if(k > 1 || head == NULL){ //判断节点树是否小于k，我觉着有点多余啊；
    	return NULL;
    }
    while(head->next != NULL){
    	chaser = chaser->next;
    	runner = runner->next;
    }
    return chaser;
}

4. 查找单链表的中间结点

依然用双指针法，代码略。

5. 从尾到头打印单链表

用栈来实现，先进后出。要么自己维护栈，要么用递归，注意链表为空的情况，还有base case. 复杂度O(n)

vector<int> printList(ListNode* head)
{
	vector<int> result;
	stack<ListNode*> s;
	ListNode* node = head;
	while(node != NULL){
	    s.push(node);
	    node = node->next;
    }
    
    while(!s.empty()){
        node = s.top();
        result.push_back(node->val);
        s.pop();
    }
    return result;
}

6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

类似于merge sort，用Divide conque，注意两个链表为空，或一个为空的情况。O(max(len1, len2))

7. 判断一个单链表中是否有环

用双指针法，如果相遇则有环，否则无环。如果要找出环的开始点，则相遇后把chaser放回head，两个指针每次走一步，相遇节点为loop起始点。
代码略。

8. 如果要遍历链表，可以考虑在head前加一个dummy node，并且检查边界条件防治数组越界(切记，出现好多次了;( )

比如swap nodes这一题，可以swap(p->val, p->next->val)，注意数组不要越界，也可以考虑在head前面加dummy node.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL){
            return head;
        }
        
        ListNode dummy(0);
        ListNode* p = &dummy; //指针指向dummy节点；
        dummy.next = head; //链接dummy和head节点
        
        while(p && p->next && p->next->next){
            ListNode* swap1 = p->next;
            ListNode* swap2 = p->next->next;
            p->next = swap2;
            swap1->next = swap2->next;
            swap2->next = swap1;
            p = p->next->next;
        }
        return dummy.next;
    }
};

注意：一个重复周期内涉及的链表先保存下一个变量，不然->next会timeout limit。并且设定初始条件链表元素数目是(head == NULL)还是(head == NULL || head->next == NULL)。

Deploy to remote sites

1	$ hexo deploy

More info: Deployment