第三天：反转链表递归写法需要巩固-创新互联

1.Swap Nodes in Pairs

创新互联是一家集网站建设,濠江企业网站建设,濠江品牌网站建设,网站定制,濠江网站建设报价,网络营销,网络优化,濠江网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode first = head, second = head.next;
        head = head.next;

        while(second != null){
            ListNode third = null;
            if(second.next != null){
                third = second.next;
            }
            second.next = first;
            if(third == null || third.next == null){
                first.next = third;
                break;
            }else{
                first.next = third.next;
                first = third;
                second = third.next;
            }
        }
        return head;
    }
}

LinkedList操作题通解：把要做的操作全列出来，找出相同的部分放进循环里。之后，再处理边界条件。
不难，大清早就做出来了。相比答案还是复杂了些。有时间研究研究递归版本。

2.Remove Nth Node From End of List

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next == null) return null;
        ListNode dummy = new ListNode(0, head);
        ListNode tmp = head, tmp2 = dummy;
        for(int i = 0; i< n; ++i) tmp = tmp.next;
        while(tmp != null){
            tmp = tmp.next; tmp2 = tmp2.next;
        }
        tmp2.next = tmp2.next.next;
        return dummy.next;  //不能return head，因为head有可能被删掉了
    }
}

思路：先让它走n个，以后让慢pointer慢慢跟。

3.Intersection of Two Linked Lists

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmp1 = headA, tmp2 = headB;
        while(tmp1 != tmp2){
            tmp1 = tmp1 == null? headB: tmp1.next;
            tmp2 = tmp2 == null? headA: tmp2.next;
        }
        return tmp1;
    }
}

相交链表核心：两个指针分别从两个链表的头开始，向前遍历。如果其中一个走完了，那么换另一个链表继续走，直到相遇为止。
相遇之后，可能都为null（则不相交）；如果都指向同一个值，就是他们相交的开始。

当然，还有笨蛋方法（但效率与此代码相同）。

1. 先求出两个链表长度。
2. 移动长链表，让两个链表在同一起跑线上。
3. 同时移动两个指针，直到他们相遇/不相遇。如果不相遇，在最后return null即可。

4.Linked List Cycle II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head, fast = head;
        while(true){
            slow = slow.next;
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            if(slow == fast) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

环形链表（找出循环的开端）核心：用fast，slow两指针，fast每次走两个，slow走一个。当它们相遇时，让两指针每次挪一格。相遇的地方就是循环的开始，因为x = z（见下文）。

算法解释：见代码随想录

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：第三天：反转链表递归写法需要巩固-创新互联
文章URL：http://cdkjz.cn/article/cejddh.html