链表之删除系列

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

Leetcode 19；medium；

删除无非就要找到要删除节点的前一个节点，但要注意边界结点的处理！

方法 1： 定义一个新链表指向 head，在dummy进行 Operation，定义 fast 和 slow 两个指针同时指向新链表的头结点，先让 fast 走 n 步，如果fast = null，那么n > 链表长度，否则 fast 和 slow 一起往下走，直到 fast 走到链表的最后一个节点，slow 指向的就是要删除节点的前一个结点；

方法 2： 在原先链表进行 Operation，定义一个 temp 指针从链表头遍历，每次 -1，遍历完后分情况讨论：当 n > 0，说明链表中根本没有倒数第 K 个节点，当 n = 0，说明倒数第 K 个节点就是链表的头元素，返回 head.next，当 n < 0，如果 n = −1，那么现在所指的就是待删除节点的前一个位置，当 n < -1，遍历当 n = -1意味着到达了待删除节点的前一个位置；

package linkedlist;

public class Main0019删除链表的倒数第N个节点 {
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		ListNode node1 = new ListNode(2);
		ListNode node2 = new ListNode(3);
		head.next = node1;
		node1.next = node2;
		ListNode node = new Solution19().removeNthFromEnd(head, 3);
		while (node != null) {
			System.out.print(node.val + " ");
			node = node.next;
		}
	}
}

// 新链表Operation
class Solution19 {
	public ListNode removeNthFromEnd(ListNode head, int n) {
		if (head == null || n < 1)
			return head;

		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode slow = dummy;
		ListNode fast = dummy;
		for (int i = 0; i < n; i++) {
			fast = fast.next;
		}
		if (fast == null) // n 大于链表的结点个数
			return head;

		while (fast.next != null) {// 让slow遍历指向删除结点的前一位置
			fast = fast.next;
			slow = slow.next;
		}
		slow.next = slow.next.next;
		return dummy.next;
	}
}

// 原链表Operation
class Solution019 {
	public ListNode removeNthFromEnd(ListNode head, int n) {
		if (head == null || n < 1)
			return head;

		ListNode cur = head;
		while (cur != null) {
			n--;
			cur = cur.next;
		}
		if (n > 0)// 说明n大于链表节点个数
			return head;
		if (n == 0)
			return head.next;

		cur = head;
		while (n < -1) { // 如果n = 0是要删除的节点,那么n = -1 就是要删除节点的前一个节点
			n++;
			cur = cur.next;
		}
		cur.next = cur.next.next;
		return head;
	}
}

// 双向链表删除倒数第N个节点
class Solution0019 {
	public DoubleNode removeNthFromEnd(DoubleNode head, int n) {
		if (head == null || n < 1)
			return head;

		DoubleNode cur = head;
		while (cur != null) {
			n--;
			cur = cur.next;
		}
		if (n > 0)
			return head;
		if (n == 0) {
			head = head.next;
			head.last = null;
			return head;
		}

		cur = head;
		while (n < -1) {
			n++;
			cur = cur.next;
		}
		// cur → cur.next → newNext
		DoubleNode newNext = cur.next.next;
		cur.next = newNext;
		if (newNext != null) {
			newNext.last = cur;
		}
		return head;
	}
}

2. 删除链表中的重复元素

Lectcode 83；easy；

如果是 有序 链表：
Key是有序！从左到右去重即可！

程序员代码面试指南（第2版）

如果是 无序 链表：
Key是无序！构造哈希表删除！

package linkedlist;

public class Main0083删除排序链表中的重复元素 {
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		ListNode node = new ListNode(2);
		ListNode node1 = new ListNode(2);
		head.next = node;
		node.next = node1;
		ListNode node2 = new Solution83().deleteDuplicates(head);
		while (node2 != null) {
			System.out.print(node2.val + " ");
			node2 = node2.next;
		}
	}
}

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

无序链表去重！

package linkedlist;

import java.util.HashSet;

public class Main删除无序单链表中值重复出现的结点 {
	public static void main(String[] args){
		ListNode head = new ListNode(1);
		ListNode node = new ListNode(2);
		ListNode node1 = new ListNode(2);
		head.next = node;
		node.next = node1;
		delRepeatNode(head);
		while (head != null) {
			System.out.print(head.val + " ");
			head = head.next;
		}
	}
	
	public static void delRepeatNode(ListNode head) {
		if (head == null)
			return;

		HashSet<Integer> set = new HashSet<>();
		set.add(head.val);
		ListNode pre = head;
		ListNode cur = head.next;
		while (cur != null) {
			if (set.contains(cur.val)) {
				pre.next = cur.next;
			} else {
				set.add(cur.val);
				pre = cur;
			}
			cur = cur.next;
		}
	}
}

3. 删除单链表中值为val的结点

程序员代码面试指南（第2版）

原链表操作！

package linkedlist;

public class Main删除无序单链表中值重复出现的结点 {
	public static void main(String[] args){
		ListNode head = new ListNode(1);
		ListNode node = new ListNode(2);
		ListNode node1 = new ListNode(2);
		head.next = node;
		node.next = node1;
		ListNode node2 = delTargetNode(head, 1);
		while (node2 != null) {
			System.out.print(node2.val + " ");
			node2 = node2.next;
		}
	}

	// 在单链表中删除指定结点val
	public static ListNode delTargetNode(ListNode head, int val) {
		while (head != null) {
			if (head.val != val) // 找到第一个不为val的结点作为头结点
				break;
			head = head.next;
		}
		ListNode pre = head;
		ListNode cur = head;
		while (cur != null) {
			if (cur.val == val)
				pre.next = cur.next;
			else
				pre = cur;
			cur = cur.next;
		}
		return head;
	}
}