【学习Java 链表题目】

1、删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
思路：
如果cur.val = cur.next.val;->cur = cur.next.next;

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return head;
    }
}

2、回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

（1）先找到中间值；
fast = fast.next.next; slow = slow.next;

（2）反转中间值后面的节点；
cur.next = slow; slow = cur; cur = curNext;

(3)用head与slow的值比较；相等则是回文结构，否则不是。

class Solution {
    public boolean isPalindrome(ListNode head) {
         if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

3、删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。题目数据保证需要删除的节点 不是末尾节点 。
解题思路：只需要把要删除的节点的值改为后一位节点的值，再删除后一位节点就可以了。

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。（用一趟扫描实现）

解题思路：定义一个傀儡节点，让fast和slow指向傀儡节点，并且保证fast和slow之间的距离等于n。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode newNode = new ListNode(-1);
        ListNode fast = newNode;
        ListNode slow = newNode;
        newNode.next = head;
        //if (n < 0 || n = 0) return head;
        while (n != 0) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        slow = slow.next;
        return newNode.next;
    }
}

4、两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路：定义一个指向head的傀儡节点，用傀儡节点来进行两个节点的交换；

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode newNode = new ListNode(-1,head);
        ListNode cur = head;
        ListNode tmp = newNode;
        while (cur != null && cur.next != null) {
            tmp.next = cur.next;
            cur.next = cur.next.next;
            tmp.next.next = cur;
            tmp = tmp.next.next;
            cur = tmp.next;
        }
        return newNode.next;
    }
}

删除排序链表中的重复元素Ⅱ

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。

找到与cur值不同的节点

tmp = curNext; cur = curNext;

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newNode = new ListNode(0,head);
        ListNode tmp = newNode;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            if (curNext != null && cur.val == curNext.val) {
                while (curNext != null && cur.val == curNext.val) {
                    curNext = curNext.next;
                }
                tmp.next = curNext;
                cur = curNext;
            }else {
                tmp = cur;
                cur = cur.next;
            }
        }
        return newNode.next;
    }
}