203. 移除鏈表元素
給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val 罐栈，請(qǐng)你刪除鏈表中所有滿足 Node.val == val 的節(jié)點(diǎn)黍衙，并返回 新的頭節(jié)點(diǎn) 。
解題思路
這道題的思路是找到第一個(gè)節(jié)點(diǎn)值不等于val的節(jié)點(diǎn)荠诬，然后判斷下一個(gè)節(jié)點(diǎn)的值是否不等于val琅翻，，如果不等于柑贞，則把當(dāng)前節(jié)點(diǎn)的next鏈接到下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)方椎，以此遍歷，直到next節(jié)點(diǎn)為空钧嘶，基于以上考慮棠众，我們可以構(gòu)建出一個(gè)虛擬節(jié)點(diǎn)，使其指向head康辑。這樣虛擬節(jié)點(diǎn)就可以作為第一個(gè)節(jié)點(diǎn)值不為val的節(jié)點(diǎn)摄欲，完成上面所說的遍歷。
代碼
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode node = new ListNode(0,head);
ListNode temp = node;
while(temp.next!=null){
if(temp.next.val == val){
temp.next = temp.next.next;
}else{
temp= temp.next;
}
}
return node.next;
}
}
總結(jié)
這道題如果不采用虛擬節(jié)點(diǎn)方式也可以實(shí)現(xiàn)疮薇，只是需要多一步找到第一個(gè)節(jié)點(diǎn)值不為val的節(jié)點(diǎn)胸墙，然后按照以上的判斷邏輯去循環(huán)遍歷好。
需要注意的點(diǎn)：如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值等于val按咒，只需要將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就好迟隅，而不用將當(dāng)前節(jié)點(diǎn)賦值到下一個(gè)節(jié)點(diǎn)。因?yàn)槲覀兪桥袛嘞乱粋€(gè)節(jié)點(diǎn)是否滿足需求励七，而賦值后智袭，下一個(gè)節(jié)點(diǎn)已經(jīng)是一個(gè)新的節(jié)點(diǎn)了，可以直接判斷
707. 設(shè)計(jì)鏈表
設(shè)計(jì)鏈表的實(shí)現(xiàn)掠抬。您可以選擇使用單鏈表或雙鏈表吼野。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值两波，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用瞳步。如果要使用雙向鏈表闷哆，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的单起。
在鏈表類中實(shí)現(xiàn)這些功能
- get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值抱怔。如果索引無效，則返回-1嘀倒。
- addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)屈留。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)测蘑。
- addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素灌危。
- addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長(zhǎng)度帮寻，則該節(jié)點(diǎn)將附加到鏈表的末尾乍狐。如果 index 大于鏈表長(zhǎng)度赠摇，則不會(huì)插入節(jié)點(diǎn)固逗。如果index小于0，則在頭部插入節(jié)點(diǎn)藕帜。
- deleteAtIndex(index)：如果索引 index 有效烫罩，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。
解題思路
這道題可以覆蓋了鏈表的常用操作洽故，我們可以采取單鏈表或者雙鏈表的方式去實(shí)現(xiàn)贝攒，而不管是采用單鏈表和雙鏈表的形式，我們都需要考慮頭節(jié)點(diǎn)或頭尾節(jié)點(diǎn)對(duì)鏈表在操作中的影響（對(duì)頭節(jié)點(diǎn)或者頭尾節(jié)點(diǎn)的特殊處理）时甚，基于這一考慮隘弊，我們可以通過虛擬頭尾節(jié)點(diǎn)的方式，來消除這種影響荒适。
代碼
單鏈表
class MyLinkedList {
private int size;
private ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(-1);
}
public int get(int index) {
ListNode listNode = getListNodeByIndex(index+1);
if(listNode == null){
return -1;
}
return listNode.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index>size){
return;
}
if(index <0){
index = 0;
}
ListNode preNode = getListNodeByIndex(index);
ListNode nextNode = preNode.next;
preNode.next = new ListNode(val,nextNode);
size++;
}
public void deleteAtIndex(int index) {
if(index<0 || index>=size){
return;
}
if(index == 0){
head = head.next;
return;
}
ListNode findNode = getListNodeByIndex(index);
ListNode nextNode = findNode.next.next;
findNode.next = nextNode;
size--;
}
/**
獲取第index節(jié)點(diǎn)梨熙，注意：第0個(gè)節(jié)點(diǎn)為虛擬節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)才是真正的第0個(gè)節(jié)點(diǎn)
所以index有效的最大值為size而不是size-1
*/
private ListNode getListNodeByIndex(int index){
if(index<0 || index>size){
return null;
}
ListNode findNode = head;
for(int i = 0;i<index;i++){
findNode = findNode.next;
}
return findNode;
}
//定義出單鏈表節(jié)點(diǎn)類
class ListNode{
public int val;
public ListNode next;
public ListNode(){
}
public ListNode(int val){
this(val,null);
}
public ListNode(int val,ListNode next){
this.val = val;
this.next = next;
}
}
}
雙鏈表
class MyLinkedList {
private int size;
private ListNode head;
private ListNode tail;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.nextNode = tail;
tail.preNode = head;
}
public int get(int index) {
if(index<0 || index>=size){
return -1;
}
ListNode findNode = getListNode(index+1);
return findNode.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index>size){
return;
}
if(index<0){
index = 0;
}
ListNode preNode = getListNode(index);
ListNode next = preNode.nextNode;
preNode.nextNode = new ListNode(val,preNode,next);
next.preNode = preNode.nextNode;
size++;
}
public void deleteAtIndex(int index) {
if(index<0||index>=size){
return;
}
ListNode findNode = getListNode(index+1);
ListNode preNode = findNode.preNode;
ListNode nextNode = findNode.nextNode;
preNode.nextNode = nextNode;
nextNode.preNode = preNode;
size--;
}
/**
根據(jù)index獲取到對(duì)應(yīng)的node刀诬，注意咽扇，這里的index是包含head和tail兩個(gè)虛擬節(jié)點(diǎn)的index
*/
private ListNode getListNode(int index){
if(index<0||index>size+1){
return null;
}
ListNode findNode;
if(index<=size/2){
findNode = head;
for(int i=0;i<index;i++){
findNode = findNode.nextNode;
}
}else{
findNode = tail;
for(int i = size+1;i>index;i--){
findNode = findNode.preNode;
}
}
return findNode;
}
public class ListNode{
int val;
ListNode preNode;
ListNode nextNode;
public ListNode(int val){
this(val,null,null);
}
public ListNode(int val,ListNode preNode,ListNode nextNode){
this.val = val;
this.preNode = preNode;
this.nextNode = nextNode;
}
}
}
總結(jié)
從以上的代碼可以看出來，添加虛擬節(jié)點(diǎn)可以很好的幫助我們解決收尾問題陕壹，因?yàn)椴还芪覀冊(cè)趺床僮髦视孜补?jié)點(diǎn)都不會(huì)被刪除，需要注意的是糠馆，因?yàn)槲覀兲砑恿颂摂M節(jié)點(diǎn)嘶伟，所以在獲取index節(jié)點(diǎn)的時(shí)候需要注意到底是獲取不包含虛擬節(jié)點(diǎn)的index還是獲取需要包含虛擬節(jié)點(diǎn)的index，例如雙鏈表在添加的時(shí)候又碌，我們是需要弄清我們到底是需要獲取新添加節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)還是后一個(gè)節(jié)點(diǎn)九昧，這對(duì)我們后續(xù)處理鏈表的操作起到了關(guān)鍵的作用盛霎。
206. 反轉(zhuǎn)鏈表
給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表耽装，并返回反轉(zhuǎn)后的鏈表愤炸。
思路
看到這道題，我們可以想到想要去反轉(zhuǎn)鏈表掉奄，那我們可以用一個(gè)節(jié)點(diǎn)記錄上一個(gè)節(jié)點(diǎn)规个，然后遍歷到當(dāng)前節(jié)點(diǎn)時(shí)，把當(dāng)前節(jié)點(diǎn)的next賦值給之前記錄的上一個(gè)節(jié)點(diǎn)姓建，那么我們可以想到使用雙指針的方式去完成诞仓，兩個(gè)指針分別指向上一個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)，然后循環(huán)去往后移動(dòng)速兔，直到當(dāng)前節(jié)點(diǎn)為null墅拭，而指向上一個(gè)節(jié)點(diǎn)的指針指向的節(jié)點(diǎn)即為新的頭節(jié)點(diǎn)
代碼
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode temp = null;
while(head!=null){
temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
}
總結(jié)
利用雙指針的方式可以比較容易的完成這題，我們用head來作為指向當(dāng)前節(jié)點(diǎn)的指針涣狗，pre用于指向上一個(gè)節(jié)點(diǎn)的指針谍婉，而pre的初始就是null，這樣一直遍歷下去镀钓，就可以將鏈表反轉(zhuǎn)穗熬，需要注意的是，遍歷完成后丁溅，head指針指向的為null唤蔗，而pre指針，指向的才是真正的新的鏈表的頭結(jié)點(diǎn)窟赏。
