算法训练营day04

一、24. 两两交换链表中的节点

题目链接：http://leetcode.cn/problems/swap-nodes-in-pairs/description/
文章讲解：http://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：http://www.bilibili.com/video/BV1YT411g7br

1.1 初见思路

• 虚拟头节点
• 三个一组
• 需返回头节点，所以需要暂存虚拟头节点

1.2 具体实现

1.2.1 方式一：虚拟头节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode pHead = new ListNode();
        pHead.next = head;
        ListNode pre = pHead;
        ListNode n1=head;
        ListNode n2 = head.next;
        ListNode nextH = null;
        while(n1!=null && n2!=null){
            nextH = n2.next;
            pre.next=n2;
            n2.next=n1;
            n1.next=nextH;

            pre=n1;
            n1=nextH;
            if(n1==null){
                break;
            }else{
                n2=n1.next;
            }
            
        }
        return pHead.next;

    }
}

1.2.2 方式二：递归

// 递归版本
class Solution {
public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;return next;
        }
    } 

1.3 重难点

• 这里的递归写法应该掌握一下，简单清晰
• 虚拟头结点主要是注意空指针异常的问题

二、 19. 删除链表的倒数第 N 个结点

题目链接：http://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
文章讲解：http://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：http://www.bilibili.com/video/BV1vW4y1U7Gf

2.1 初见思路

这个题做了很多遍了，快慢指针，不算难

2.2 具体实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre= new ListNode();
        pre.next=head;
        ListNode fast = pre;
        ListNode cur = pre;
        
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        while(fast!=null){
            cur=cur.next;
            fast=fast.next;
        }
        if(cur.next!=null){
            cur.next = cur.next.next;
        }
        return pre.next;
    }
}

2.3 重难点

• 快慢指针
• 用虚拟头节点，同时慢指针也从虚拟头节点开始，这样能方便删除点位

三、 面试题 02.07. 链表相交

题目链接：http://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
文章讲解：http://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：http://www.bilibili.com/video/BV12A4y1Z7LP

3.1 初见思路

1. 计算两条链表长度差值k
2. 两个链表各自一个指针，长链表指针先移动k
3. 然后两个指针再一起移动，看是否有相同的节点

3.2 具体实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA=0;
        int sizeB=0;
        ListNode tA = headA;
        ListNode tB = headB;
        ListNode curA = headA;
        ListNode curB = headB;
        while(tA!=null){
            sizeA++;
            tA=tA.next;
        }
        while(tB!=null){
            sizeB++;
            tB=tB.next;
        }
        if(sizeA>sizeB){
            int diff = sizeA-sizeB;
            //A队列指针先移动diff
            for(int i=0;i<diff;i++){
                curA=curA.next;
            }
        }else{
            int diff=sizeB-sizeA;
            for(int i=0;i<diff;i++){
                curB=curB.next;
            }
        }
        while(curA!=null && curB!=null){
            if(curA==curB){
                return curA;
            }
            else{
                curA=curA.next;
                curB=curB.next;
            }
        }
        return null;
        
    }
}

3.3 重难点

• 无

四、 142.环形链表II

题目链接：http://leetcode.cn/problems/linked-list-cycle-ii/description/
文章讲解：http://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：http://www.bilibili.com/video/BV12A4y1Z7LP

4.1 初见思路

• 判断是否成环，用快慢指针即可
• 如何找到环的入口，需要用到初中数据的知识

4.2 具体实现

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;
    }
}

4.3 重难点

• 如何判断入口