第 18-1 题：在 )
时间删除链表结点（多写几遍）
给定单向链表的一个节点指针，定义一个函数在
假设链表一定存在，并且该节点一定不是尾节点。
样例：
输入：链表
1->4->6->8，删掉节点：第 2 个节点即 6（头节点为第 0 个节点）输出：新链表
1->4->8
思路：待删除的结点是末尾结点的情况比较容易忽略，刚好题目中说“该节点一定不是尾节点”。
Python 代码：
# 28. 在O(1)时间删除链表结点
# 给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
#
# 假设链表一定存在，并且该节点一定不是尾节点。
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void
"""
next = node.next
node.val = next.val
node.next = next.next
next.next = None
C++ 代码：
image-20190108002212753
第 18-2 题：删除链表中重复的结点
同 LeetCode 第82 题。
传送门：AcWing：删除链表中重复的节点，牛客网 online judge 地址。
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。
样例1：
输入：
1->2->3->3->4->4->5输出：
1->2->5样例2：
输入：
1->1->1->2->3输出：
2->3
思路：因为头结点可能被删，所以要设置一个虚拟头结点。
Python 写法：
class Solution(object):
def deleteDuplication(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
dummy = ListNode(-1)
dummy.next = head
cur = dummy
# 一下子要看两个，所以是
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
# 删除的起点至少是 cur.next.next
del_node = cur.next.next
while del_node.next and del_node.val == del_node.next.val:
del_node = del_node.next
# 来到了一个新的结点，值不同
cur.next = del_node.next
del_node.next = None
else:
cur = cur.next
return dummy.next
Java 代码：
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = pHead;
ListNode curNode = dummyNode;
while (curNode.next != null && curNode.next.next != null) {
ListNode next = curNode.next;
ListNode nextNext = next.next;
if (next.val == nextNext.val) {
while (nextNext.next != null && nextNext.val == nextNext.next.val) {
nextNext = nextNext.next;
}
ListNode delNode = nextNext;
curNode.next = delNode.next;
delNode.next = null;
} else {
curNode = curNode.next;
}
}
return dummyNode.next;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 2, 3, 3, 4, 4, 5};
ListNode head = new ListNode(nums);
System.out.println(head);
Solution solution = new Solution();
ListNode deleteDuplication = solution.deleteDuplication(head);
System.out.println(deleteDuplication);
}
}
LeetCode 第 82 题： 删除排序链表中的重复元素 II
传送门：82. 删除排序链表中的重复元素 II。
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入:
1->2->3->3->4->4->5
输出:1->2->5示例 2:
输入:
1->1->1->2->3
输出:2->3
Java 代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
// 只要涉及头结点的操作，我们都设立虚拟头结点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode curNode = dummyNode;
while (curNode.next != null && curNode.next.next != null) {
// 如果接连两个结点的 val 相等，至少要把它们都删掉
if (curNode.next.val == curNode.next.next.val) {
// 要删除的起点至少应该是当前判断相同的结点的第 2 个
ListNode delNode = curNode.next.next;
// 如果后面还有相同的结点，delNode 后移一位，即 delNode 应该是指向相同的结点的最后一个
while (delNode.next != null && delNode.next.val == delNode.val) {
delNode = delNode.next;
}
curNode.next = delNode.next;
delNode.next = null;
} else {
curNode = curNode.next;
}
}
return dummyNode.next;
}
}
LeetCode 第 83 题： 删除排序链表中的重复元素
传送门：83. 删除排序链表中的重复元素。
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2 输出: 1->2示例 2:
输入: 1->1->2->3->3 输出: 1->2->3
Java 代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode curNode = head;
while (curNode != null && curNode.next != null) {
if (curNode.val == curNode.next.val) {
ListNode delNode = curNode.next;
// 继续向前找，看看，还有没有可以删除的结点
while (delNode.next != null && delNode.next.val == delNode.val) {
delNode = delNode.next;
}
// 穿针引线
curNode.next = delNode.next;
delNode.next = null;
} else {
curNode = curNode.next;
}
}
return head;
}
}
