赞
踩
当涉及到数据结构时,链表是一种常见且重要的数据结构。链表由一系列节点组成,每个节点包含数据和指向下一个节点的引用。相比于数组,链表的大小可以动态地增长或缩小,因为每个节点只需要存储自己的数据和指向下一个节点的引用。
首先,我们需要定义一个表示链表节点的类。节点类应该包含一个数据字段和一个指向下一个节点的引用字段。可以使用泛型来使节点类更加通用。
class ListNode<T> {
T data;
ListNode<T> next;
public ListNode(T data) {
this.data = data;
this.next = null;
}
}
接下来,我们可以创建一个链表类,它包含对链表进行操作的方法,如插入节点、删除节点和遍历链表等。
class LinkedList<T> { private ListNode<T> head; public LinkedList() { this.head = null; } // 在链表头部插入节点 public void insertAtHead(T data) { ListNode<T> newNode = new ListNode<>(data); newNode.next = head; head = newNode; } // 在链表尾部插入节点 public void insertAtTail(T data) { ListNode<T> newNode = new ListNode<>(data); if (head == null) { head = newNode; } else { ListNode<T> current = head; while (current.next != null) { current = current.next; } current.next = newNode; } } // 删除指定节点 public void deleteNode(T data) { if (head == null) { return; } if (head.data.equals(data)) { head = head.next; return; } ListNode<T> current = head; while (current.next != null) { if (current.next.data.equals(data)) { current.next = current.next.next; return; } current = current.next; } } // 遍历链表并打印节点数据 public void printList() { ListNode<T> current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } }
现在,我们可以使用链表类来创建链表对象,并进行插入、删除和遍历等操作。
public class Main {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.insertAtHead(3);
linkedList.insertAtHead(2);
linkedList.insertAtHead(1);
linkedList.insertAtTail(4);
linkedList.printList(); // 输出: 1 2 3 4
linkedList.deleteNode(2);
linkedList.printList(); // 输出: 1 3 4
}
}
这就是一个简单的链表教程,它展示了如何使用Java语言来实现链表的基本操作。通过理解链表的结构和使用方法,你可以在编程中灵活地应用链表来解决各种问题。
双向链表(Doubly Linked List)是一种链表的变体,每个节点除了包含数据和指向下一个节点的引用外,还包含指向前一个节点的引用。这使得双向链表可以在正向和反向两个方向上遍历。
下面是一个用Java语言描述双向链表的简单教程:
首先,我们需要定义一个表示双向链表节点的类。节点类应该包含一个数据字段,一个指向前一个节点的引用字段和一个指向后一个节点的引用字段。同样,可以使用泛型来使节点类更加通用。
class DoublyListNode<T> {
T data;
DoublyListNode<T> prev;
DoublyListNode<T> next;
public DoublyListNode(T data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
接下来,我们可以创建一个双向链表类,它包含对双向链表进行操作的方法,如插入节点、删除节点和遍历链表等。
class DoublyLinkedList<T> { private DoublyListNode<T> head; public DoublyLinkedList() { this.head = null; } // 在链表头部插入节点 public void insertAtHead(T data) { DoublyListNode<T> newNode = new DoublyListNode<>(data); if (head == null) { head = newNode; } else { newNode.next = head; head.prev = newNode; head = newNode; } } // 在链表尾部插入节点 public void insertAtTail(T data) { DoublyListNode<T> newNode = new DoublyListNode<>(data); if (head == null) { head = newNode; } else { DoublyListNode<T> current = head; while (current.next != null) { current = current.next; } current.next = newNode; newNode.prev = current; } } // 删除指定节点 public void deleteNode(T data) { if (head == null) { return; } if (head.data.equals(data)) { head = head.next; if (head != null) { head.prev = null; } return; } DoublyListNode<T> current = head; while (current != null) { if (current.data.equals(data)) { current.prev.next = current.next; if (current.next != null) { current.next.prev = current.prev; } return; } current = current.next; } } // 遍历链表并打印节点数据 public void printList() { DoublyListNode<T> current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } }
现在,我们可以使用双向链表类来创建双向链表对象,并进行插入、删除和遍历等操作。
public class Main {
public static void main(String[] args) {
DoublyLinkedList<Integer> doublyLinkedList = new DoublyLinkedList<>();
doublyLinkedList.insertAtHead(3);
doublyLinkedList.insertAtHead(2);
doublyLinkedList.insertAtHead(1);
doublyLinkedList.insertAtTail(4);
doublyLinkedList.printList(); // 输出: 1 2 3 4
doublyLinkedList.deleteNode(2);
doublyLinkedList.printList(); // 输出: 1 3 4
}
}
这就是一个简单的双向链表,它展示了如何使用Java语言来实现双向链表的基本操作。通过理解双向链表的结构和使用方法,你可以在编程中灵活地应用双向链表来解决各种问题。
ListNode
public class ListNode { int val; ListNode next; ListNode prev; public ListNode() { } ListNode(int x) { val = x; next = null; } ListNode(int x, ListNode next) { val = x; this.next = next; } ListNode(int x, ListNode next, ListNode prev) { val = x; this.next = next; this.prev = prev; } }
public ListNode deleteDuplicates(ListNode head) { if (head == null) { return null; } ListNode dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; }
现在要把所有的重复元素全部删除要怎么做?
public ListNode deleteDuplicatesAll(ListNode head) { if (head == null) { return null; } ListNode dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { cur.next = cur.next.next; int x = cur.next.val; while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; } } else { cur = cur.next; } } return dummy.next; }
这段代码实现了删除链表中所有重复的节点。下面是对代码的解析和题解:
dummy
,将其指向头节点 head
。这样做是为了方便处理头节点可能被删除的情况。cur
来遍历链表,初始时指向虚拟节点 dummy
。cur
的下一个节点 cur.next
和下下个节点 cur.next.next
是否存在。如果两个节点的值相等,说明存在重复节点。cur.next
指向下下个节点 cur.next.next
,跳过重复节点。x
记录被删除的重复节点的值,然后继续循环,删除链表中所有与 x
相等的节点。cur.next
和 cur.next.next
的值不相等,说明当前节点没有重复,将 cur
移动到下一个节点。dummy
的下一个节点作为新的链表头节点。这段代码的时间复杂度为
O
(
n
)
O(n)
O(n),其中
n
n
n 是链表的长度,因为我们只遍历了一次链表。空间复杂度为
O
(
1
)
O(1)
O(1),只使用了常数级别的额外空间。
可以有效地删除链表中所有重复的节点,保留不重复的节点。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。