链表算法学习

链表基础

移除链表

问题：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。

这个问题很简单，不需要过多进行说明，但在解题的过程中会碰到各种各样隐形的问题，比如NullPointerException、要考虑头结点需要删除时的情况等等，对于头结点的特殊处理，可以采用添加虚拟节点再进行统一处理，也可以不添加虚拟节点特殊情况特殊解决，采用虚拟节点的方法感觉会简单一些。

我得到的经验就是，在链表解题时进行条件判断逻辑与运算时，要把判断null放在判断值之前，否则很容易出现NullPointerException，因为如果第一个条件就不成立了，就不会再去判断后面的条件了。

二刷思考：要注意在删除节点的时候，cur节点就不要再往前移动了，移进的话遇到连续需要删除的元素会出现问题。

代码示例：

//不添加虚拟节点的方法
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;

//添加虚节点方法
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}
}

设计链表

问题：使用单链表或者双链表，设计并实现自己的链表，单链表中的节点应该具备两个属性：val和next。val是当前节点的值，next是指向下一个节点的指针/引用，要实现链表中下标为index的节点的值、节点插入到链表中第一个元素之前、节点追加到链表中作为链表的最后一个元素、插入到链表中下标为index的节点之前、删除链表中下标为index的节点。

一道有些麻烦但不难的题，主要要弄清楚链表和其节点的定义和特性，想必这题会对ACM模式下如何编写链表结构有很大的帮助，代码就不放在这里了，以后练习ACM模式的算法题应该不会少训练到。

两两交换链表中的节点

问题：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表，你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

一道简单的模拟过程，不需要多说什么，我主要是以此题强化了对于虚拟头节点的理解。该题若是不适用虚拟头节点，则需要考虑head是否为空，head.next又是否为空的情况，在限定条件不够充分的情况下，很容易出现NullPointerException，而若是使用了虚拟头结点，可以避免head.next出现异常的情况，非常好用。

代码示例：

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;  
    }
}

双指针

链表相交

问题：给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。

解决这个问题主要是要消除两条链表的路程差，我们让其从同一位置开始出发，若相交，在若干步之后一定会有两条链表的节点相遇，返回该节点即可。我们可以先求出链表长度，计算出长度差，让长一些的链表节点先行移动这么多；也可以移动通过移动两趟来消除路程差，道理都是一样的。

代码示例：

(版本二) 合并链表实现同步移动
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// p1 指向 A 链表头结点，p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 链表末尾，转到 B 链表
			if (p1 == null) p1 = headB;
			else            p1 = p1.next;
			// p2 走一步，如果走到 B 链表末尾，转到 A 链表
			if (p2 == null) p2 = headA;
			else            p2 = p2.next;
		}
		return p1;
    }
}

环形链表II

问题：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

这题待我用纸笔推导一下。

代码示例：

public 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 index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

翻转链表

问题：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。首先要把 cur->next 节点用tmp指针保存一下,改变 cur->next 的指向，将cur->next 指向pre，再继续向右移动pre和cur指针。递归法道理和双指针法是一样的，在这里不过多赘述。

代码示例：

//双指针
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}