leetcode反转链表全家桶

/**
 * 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 reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

/**
 * 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 reverseKGroup(ListNode head, int k) {

        //创建dummy节点方便输出
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        //pre为需要翻转的链表的头节点的前一个节点
        //end为需要翻转的链表的最后一个节点
        ListNode pre = dummy;
        ListNode end = dummy;

        while(end.next != null){
            //移动end节点，但遇见空指针就停，表示已到表尾，剩余不足k，不用翻转
            //足够的话循环会正常结束，不会因为end == null 而结束
            for(int i = 0 ; i < k && end != null; i++) end = end.next;
            if(end == null) break;

            //start为需要翻转的链表的头结点，next为下一段需要翻转的链表的头结点
            ListNode start = pre.next;
            ListNode next = end.next;

            /* 
            * 两行一起看，end.next为什么要等于null？(断开链表)
            * 因为reverse函数的while循环里判断当前指针是否为null就可以结束循环
            * 而不用计数器翻转了n个结点结束
            */
            end.next = null;
            pre.next = reverse(start);

            //翻转完毕后，start节点变成了翻转后的最后一个，需要与未翻转的链表连接起来
            //此时的start为下一段需要翻转的链表的头节点的前一个节点，即pre
            //end也从这个地方重新开始计数
            start.next = next;
            pre = start;
            end = start;
        }
        return dummy.next;
    }

    //简单的双指针翻转链表，leetcode206题
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode preHead = new ListNode(0);
        //pre用来存储需要删除的部分链表的前一个节点
        ListNode pre = preHead;
        ListNode cur = head;
        preHead.next = head;
        while(cur != null){
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            //pre的下一个不是cur，pre后面的和cur前面的（包括cur）都是重复元素
            if(pre.next != cur){
                pre.next = cur.next;
                cur = cur.next;
            }
            //pre的下一个就是cur，没有重复元素，往后移
            else{
                pre = cur;
                cur = cur.next;
            }
        }
        return preHead.next;
    }
}