随想录一期 day4 [24. 两两交换链表中的节点|19. 删除链表的倒数第 N 个结点|面试题 02.07. 链表相交|142. 环形链表 II]

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

思路

• 换图分析要交换的节点
• 待交换节点一定有两个节点才能满足交换条件，顾循环条件为pre.next和pre.next.next

复杂度

• 时间 O(n)
• 空间 O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head ;
        ListNode pre = dummy ,cur = null ,next =  null;
        while(pre.next != null && pre.next.next!= null){
            //交换的节点cur和next
            cur = pre.next ;
            next = cur.next ;
            cur.next = next.next ;
            next.next = cur ;
            
            pre.next = next ;
            pre = cur ;

             
        }
        return dummy.next ;
    }
}

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

思考

• 快慢双指针思想，快指针先走k步后，快慢同步
• 若快指针为null时，说明删除的是头结点，即return head.next即可
• pre节点记录要删除的节点的上一个节点

复杂度

• 时间 O(n) （n为索引操作的值）
• 空间 O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head ,fast = head ;
        while(n>0){
            fast = fast.next ;
            --n;
        }
        if(fast == null) return head.next;
        ListNode pre = null;
        while(fast != null){
            pre = slow ;
            slow = slow.next ;
            fast = fast.next ;
        }
        pre.next = slow.next ;
        
        return head; 
    }
}

面试题 02.07. 链表相交

思考

• 暴力解法，试用列表存储两个链表的每个节点，若发现已存在则为相遇第一个节点

复杂度

• 时间 O(n)
• 空间 O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA ==null || headB == null) return null;
        Set<ListNode> sets = new HashSet<>();
        ListNode cur = headA;
        while(cur != null){
            if(sets.contains(cur)){
                return cur ;
            }
            sets.add(cur);
            cur = cur.next ;
        }
        cur = headB ;
        while(cur != null){
            if(sets.contains(cur)){
                return cur ;
            }
            sets.add(cur);
            cur = cur.next ;
        }
        

        return null ;
    }
}

高级解法

• 循环条件A!=B ，第一轮较短的链表先结束，结束后长链表引用赋值给短链表，继续循环N步时，长链表结束，短链表赋值给长链表，即N为两个链表长度之差，先结束的已经又走了N步，此时长短处于同一位置
• 若有重合节点，则直接返回，若无则最终两节点都为null，结束循环

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

参考图形解析

142. 环形链表 II

思考

• 环形链表解法可想到快慢双指针得到环中相遇节点
  • 相遇节点时，slow走的步数和fast走的步数一定是环形节点数量的整数倍nK
  • 所以找到任意一个相遇节点C距离首节点的步数一定为K的倍数，此时从头结点出发T，以相同步伐和C相遇时，即为链表入口节点
• 核心思想：环形链表中节点的数量为快指针先走的步数，此时同步移动，得到入口节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode node = getInNodeLoop(head);
        if(node == null){
            return null; 
        }
        ListNode tmp = head ;
        while(tmp != node){
            tmp = tmp.next;
            node = node.next;
        }
        return node ; 

    }
    //快慢指针得到任意相遇节点
    public ListNode getInNodeLoop(ListNode head){
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head.next ,fast=slow.next;
        while(slow != null && fast != null){
            if(slow == fast){
                return slow ;
            }
            slow = slow.next ;
            fast = fast.next ;
            if(fast != null){
                fast = fast.next ; 
            }
        }
        return null;

    }
}

总结

• 链表题型的几种指针

  • 左右同步指针（边向中间靠拢）
  • 同向快慢指针（一般快指针速度为慢指针速度的2倍）
  • 左右同步指针（中间向两边扩散）

  fast = fast.next ;
  if(fast != null){
  fast = fast.next ;
  }
  }
  return null;

  }
  }

### 总结

+ 链表题型的几种指针
  + 左右同步指针（边向中间靠拢）
  + 同向快慢指针（一般快指针速度为慢指针速度的2倍）
  + 左右同步指针（中间向两边扩散）