什么时候用Dummy -- 如果链表本身改变

61. Rotate List

链表节点放到函数里面作为Object是不能改变的 所给的K 可能会大于链表长要取余数 指针记录几个移动的点 画图好

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null)return head;
        ListNode first = head;
        ListNode p1 = head;
        int len = getLen(p1);
        for(int i = 0;i < len - 1;i++){
            p1 = p1.next;
        }
        k = k % len;
        k = len - k;
        if(k == 0)return head;
        //move the pointer to the kth index
        ListNode p2 = head;
        for(int i = 0;i < k - 1;i++){
            p2 = p2.next;
        }
        ListNode res = p2.next;
        p2.next = null;

        p1.next = first;
        return res;
    }
    public int getLen(ListNode p){
        int len = 0;
        while(p != null && p.next != null){
            p = p.next;
            len++;
        }
        return len + 1;
    }
}

Reverse

206. Reverse Linked List

public class Solution {
    public ListNode reverseList(ListNode head) {
        //
        ListNode pre = null;
        while(head != null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

25. Reverse Nodes in k-Group

两个指针维护大小达为K的区间~到K的个数的时候 Reverse这个区间 并返回区间末尾(reverse 完的) 在这之前是保存了当前指针Cur的下一个的 然后清除计数器

Reverse 函数 : pre--1--2--3--next : pre ---3--2---1---next

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            ListNode next = cur.next;
            if(count == k){
                pre = reverse(pre,next);
                count = 0;
            }
            cur = next;
        }
        return dummy.next;
    }
    //pre--1-->2-->3-->4--->end , pre-->4..>3-->2-->1-->end
    public ListNode reverse(ListNode pre,ListNode end){
        if(pre == null || pre.next == null)return pre;
        ListNode head = pre.next;
        ListNode cur = pre.next.next;
        while(cur!= end){
            ListNode next = cur.next;  
            cur.next = pre.next;  
            pre.next = cur;  
            cur = next; 
        }
        head.next = end
        return head;
    }
}

160. Intersection of Two Linked Lists

注意如果采用指针移动法 并不能确认！！因为呢 两边每次走一步 如果两个链表的长度不一样则不行 所第一个傻瓜做法就是求出两个链表的长度然后对齐..这个是我能想到的解法

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        ListNode p1 = headA;
        ListNode p2 = headB;
        int len1 = getLen(headA);
        int len2 = getLen(headB);
        int div = Math.abs(len1 - len2);
        //Aligh the two starting nodes together 
        if(len1 > len2){
            while(len1 > len2){
                p1 = p1.next;
                len1--;
            }
        }
        else if(len1 < len2 ){
            while(len1 < len2){
                p2 = p2.next;
                len2--;
            }
        }
        //compare one by one for the remaining nodes with the same length
        while(p1 != null){
            if(p1==p2)return p1;
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
    //retrieve the length of a LinkedList to compute the difference 
    public int getLen(ListNode head){
        ListNode p = head;
        int len = 0;
        while(p!=null){
            p = p.next;
            len++;
        }
        return len;
    }
}

24. Swap Nodes in Pairs

弄清前面三个怎么swap 的 看好指针P下一步要指到哪里 一般我们在变换之前都要保存原来的位置 这里是要形成新的链表 所以我们需要用Dummy

public class Solution {
    //又是新的List,所以用Dummy!链表操作题 把前后想清楚了画出来就没有问题
    public ListNode swapPairs(ListNode head) {
        if(head == null)return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        while (p.next!=null && p.next.next!=null) {
            ListNode first = p.next;
            ListNode second = first.next;
            ListNode third = second.next;
            p.next = second;
            second.next = first;
            first.next = third;
            //Important! Where do we place the next starting node
            p = first;
        }
        return dummy.next;
    }
}

25. Reverse Nodes in k-Group