【刷题笔记】链表篇

今天一直在刷题，没有来得及学一些知识，就分享一下今天的刷题心得吧。

1. 206. 反转链表

public ListNode reverseList(ListNode head) {
	return reverse(head, null);
}
    
private static ListNode reverse(ListNode head, ListNode tail) {
	if(head == null) {
		return tail;
	}
	ListNode temp = head.next;
	head.next = tail;
	return reverse(temp, head);
}

递归是关键：每次递归时要分清每个参数的真实意义，比如在进入reverse(temp, head) 后temp就是下一轮递归的head，而head则是下一轮递归的tail。

2. 24. 两两交换链表中的节点

public ListNode swapPairs(ListNode head) {
    ListNode dumyhead = new ListNode(-1, head);
    ListNode cur = dumyhead;
    ListNode temp1 = null;
    ListNode temp2 = null;
    while(cur.next != null && cur.next.next != null) {
        temp1 = cur.next;
        temp2 = cur.next.next.next;
        cur.next = cur.next.next;
        temp1.next = temp2;
        cur.next.next = temp1;
        cur = temp1;            
    }
    return dumyhead.next;
}

这个题本身逻辑不难，易错点在于要经过多次改变节点指向后要知道当前节点在哪，头节点在哪。

3.19. 删除链表的倒数第 N 个结点

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode(-1,head);
    ListNode fast = dummyHead;
    ListNode slow = dummyHead;
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummyHead.next;
}

这道题尤其要注意空指针的问题，当你的链表只有一个节点的时候，如果你在用双指针的方法不进行处理，你这个头节点就无法删掉，一定会报空指针异常。

所以在做链表相关题目的时候一定要考虑几个问题：（1） 当前链表是一个[]

                                                                                   （2） 当前链表只有一个节点（删除问题）

                                                                                   （3）考虑while循环里面的条件

4. 面试题 02.07. 链表相交

这道题还是比较有意思的，我参考答案整理了三种方法。

1）这道题的原理是，如果两个单向链表有交点，那么他们自交点后一定是一样长的，也就是说从尾巴开始往前一直到第一个相同节点，两个链表都是一样的。那么我们就可以让他们的尾巴对齐，然后长的那个链表跳到和短的链表相同的位置，再一起向后跳，每跳一次比较这两个节点是否相等（val和next都要相等），直到找到为止。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int index1 = 0;
        int index2 = 0;
        while (cur1 != null) {
            cur1 = cur1.next;
            index1++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            index2++;
        }
        cur1 = headA;
        cur2 = headB;
        int diff = index1 - index2;
        if (diff >= 0) {
            for (int i = 0; i < diff; i++) {
                cur1 = cur1.next;
            }
        } else {
            for (int i = 0; i < -diff; i++) {
                cur2 = cur2.next;
            }
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                break;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

2）方法二采用了hashSet。利用hashSet先把第一个链表中的节点都装进去，然后从第二个链表的头开始遍历，看看是否hashSet包含这个节点，如果包含，第一个找到的节点就是我们要找的。原因是：单向链表的next只有一个，不能分叉，所以只要找到第一个相同的节点，那么它就一定是。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur = headA;
        Set<ListNode> set = new HashSet<>();
        while (cur != null) {
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            if (set.contains(cur)) {
                break;
            }
            cur = cur.next;
        }
        return cur;
    }

3）方法三，采用了双指针的做法。它的思路其实和方法一是一致的，本质上还是让两个链表的尾巴对齐，然后到了两个链表一样长的位置，一起往后跳，直到找到第一个相同的节点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        if (headA == null || headB == null) {
            return null;
        }
        while (cur1 != cur2) {
            if (cur1 == null) {
                cur1 = headB;
            } else {
                cur1 = cur1.next;
            }
            if (cur2 == null) {
                cur2 = headA;
            } else {
                cur2 = cur2.next;
            }
        }
        return cur1;
    }