題目要求
刪除鏈表中重復(fù)的節(jié)點(diǎn)爱榔。
重復(fù)的節(jié)點(diǎn)：
當(dāng)前節(jié)點(diǎn)的值與下一個(gè)節(jié)點(diǎn)的值相等被环，那么稱(chēng)這兩個(gè)節(jié)點(diǎn)為重復(fù)的節(jié)點(diǎn)
題目解析
思路一：
- 分析
假設(shè)該鏈表為2、3详幽、3筛欢、4浸锨、4、5
刪除完畢之后變?yōu)?版姑、5
那么如果是2柱搜、2、5剥险、6
刪除完畢之后成為5聪蘸、6。這個(gè)時(shí)候需要改變頭結(jié)點(diǎn)表制，所以我們必須返回新的頭結(jié)點(diǎn)
另外還需要考慮的是如果是2健爬、2、2
那么刪除完畢之后么介，鏈表為空娜遵。
情況分析完畢，現(xiàn)在我們來(lái)看如何對(duì)重復(fù)的節(jié)點(diǎn)進(jìn)行刪除壤短。
首先從頭結(jié)點(diǎn)開(kāi)始遍歷设拟，檢查當(dāng)前節(jié)點(diǎn)的值curValue是否與下一個(gè)節(jié)點(diǎn)的值相等。如果相等繼續(xù)檢查再下一個(gè)節(jié)點(diǎn)是否相等鸽扁。
直到發(fā)現(xiàn)不相等的蒜绽，將最后一個(gè)相等的節(jié)點(diǎn)的next值賦給第一個(gè)相等的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next。
如果head節(jié)點(diǎn)就是相等的節(jié)點(diǎn)桶现，那么我們?cè)趧h除以后要注意改變鏈表的頭結(jié)點(diǎn)躲雅。
- 代碼段
public static ListNode deleteRepeatNode(ListNode head) {
//定義一個(gè)輔助節(jié)點(diǎn)記錄刪除區(qū)間的前一個(gè)節(jié)點(diǎn)
ListNode preNode = null ;
//定義一個(gè)輔助節(jié)點(diǎn)記錄頭結(jié)點(diǎn)
ListNode headNode = head ;
//定義一個(gè)輔助標(biāo)記是否有重復(fù)的節(jié)點(diǎn)
boolean hasRepeat = false ;
//判空
if(head == null) {
return headNode ;
}
//從head開(kāi)始往尾節(jié)點(diǎn)遍歷
while( head != null && head.getNext() != null) {
//遍歷有多少個(gè)重復(fù)的節(jié)點(diǎn)
while( head.getNext() != null && head.getValue() == head.getNext().getValue()) {
head = head.getNext() ;
hasRepeat = true ;
}
if (hasRepeat) {
//如果存在了重復(fù)的節(jié)點(diǎn),那么進(jìn)行刪除處理
if(preNode == null) {
headNode = head.getNext() ;
}else {
preNode.setNext(head.getNext());
}
}else {
//如果不存在，記錄當(dāng)前不存在的節(jié)點(diǎn)骡和，作為preNode ;
preNode = head ;
}
head = head.getNext() ;
}
return headNode ;
}
測(cè)試代碼
public static void main(String[] args) {
ListNode node1 = new ListNode() ;
ListNode node2 = new ListNode() ;
ListNode node3 = new ListNode() ;
ListNode node4 = new ListNode() ;
ListNode node5 = new ListNode() ;
ListNode head = null ;
node1.setValue(1);
node2.setValue(1);
node3.setValue(3);
node4.setValue(3);
node5.setValue(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
head = deleteRepeatNode(node1) ;
showListNode(head);
node1.setValue(1);
node2.setValue(2);
node3.setValue(3);
node4.setValue(4);
node5.setValue(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
head = deleteRepeatNode(node1) ;
showListNode(head);
node1.setValue(1);
node2.setValue(1);
node3.setValue(1);
node4.setValue(1);
node5.setValue(1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
head = deleteRepeatNode(node1) ;
showListNode(head);
ListNode nullNode = null ;
head = deleteRepeatNode(nullNode) ;
showListNode(head);
}
運(yùn)行結(jié)果
5
1 2 3 4 5
