【代码随想录算法训练营-第四天】【链表】24，19， 面试题 02.07，142

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

第一遍-递归-小看了一下题解

• 思路：
  • 读了两遍题目才理解…
  • 相邻节点的交换，这个操作很容易实现，但需要一个tmpNode
  • 因为是链表的题目，没开始思考之前先加了dummyNode，还真管用
  • 把dummyNode作为了最后返回用的，以及新增preNode作为tmpNode
  • 用递归写是因为不想用循环了…感觉递归写起来好玩一些
  • 小看了一下题解的地方：（其实再给自己多一些debug的次数应该也能试出来）
    • 递归结束条件：|| i.next.next == null这个没有想出来

/*
* 这部分是自己在Idea上写的，用了之前的题目实现的MyLinkedList
* 感觉这样会比在力扣上面写更能熟悉链表一些，而且debug更容易一些
* */
package LinkList;


public class Linklist_test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtHead(4);
        myLinkedList.addAtHead(3);
        myLinkedList.addAtHead(2);
        myLinkedList.addAtHead(1);
        LinklistSolution solution = new LinklistSolution();
        ListNode head = solution.swapPairs(myLinkedList.dummy.next);
        for (; head != null; head = head.next) {
            System.out.println(head.val);
        }
    }
}

class LinklistSolution {
    public ListNode reverseDouble(ListNode head, ListNode preNode, ListNode i, ListNode j) {
        // 交换节点
        preNode.next = i.next;
        i.next = j.next;
        j.next = i;
        if (i.next == null || i.next.next == null) return head.next;
        // 移动节点
        j = i.next.next;
        i = i.next;
        preNode = preNode.next.next;
        return reverseDouble(head, preNode, i, j);
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode preNode = dummy;
        ListNode i = head;
        ListNode j = head.next;
        return reverseDouble(dummy, preNode, i, j);
    }
}

• 看了一下代码随想录Java的递归题解，嗯，真🐂，我想不出来
  • 示例代码很好的利用了链表是通过指向下一个节点的地址链接的，所以返回newNode可以实现；

// 示例代码
class LinklistSolution {
    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;
    }
}

19.删除链表的倒数第N个节点

第一遍

• 思路：
  • 这一题误操作了，忘记先自己想了，直接看题解了…
  • 算是两遍AC吧，第一次fast指针的循环没控制好

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        if (head.next == null) {
            return head.next;
        }
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        for (; fast != null; fast = fast.next) {
            slow = slow.next;
            // fast = fast.next; 第一次提交的时候多写了一个这个，debug的时候才发现不对
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

面试题 02.07. 链表相交

第一遍

• 思路：
  • 读了第一遍直接写了，第一次开始写循环又出错了…而且出了两个错误
    • 错误1：判断条件写成了A.next != null，导致所有的链表长度都-1，长度为1且相交的时候会有问题；
    • 错误2：没有写A = A.next的修改条件；
  • 第一遍写完，使用的是A.val = B.val的判断条件，不对，发现有val相等，但是答案并不是对应指针；
  • 麻了，又去看题，看了n遍都没看懂；
  • 最后看了题解，结果发现是指针相等（怎么从题中读出的指针相等的？）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        int lenA = 0, lenB = 0;
        while (A != null) {
            lenA++;
            A = A.next;

        }
        while (B != null) {
            lenB++;
            B = B.next;
        }
        A = headA;
        B = headB;
        int n = lenA >= lenB ? lenA - lenB : lenB - lenA;
        int m = lenA >= lenB ? lenB : lenA;
        if (lenA > lenB) {
            while (n > 0) {
                A = A.next;
                n--;
            }
        } else {
            while (n > 0) {
                B = B.next;
                n--;
            }
        }
        while (m > 0) {
            if (A == B) {
                return A;
            }
            A = A.next;
            B = B.next;
            m--;
        }
        return null;
    }
}

142.环形链表II

第一遍-看题解后一遍过

• 思路：
  • 20mins的思考，想到了slowNode每次+1，fastNode每次+2；
  • 但这样单纯的移动，会导致两个点相遇的时候不在入口，答案错误；
  • 最后还是看了题解，感觉不太能想得出来；

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if (fastNode == slowNode) {
                while (head != fastNode) {
                    head = head.next;
                    fastNode = fastNode.next;
                }
                return head;
            }
        }
        return null;
    }
}