1.移除鏈表元素
刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)定续。
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode removeElements(ListNode head, int val) {
ListNode dy = new ListNode(-1);
dy.next = head;
ListNode curNode = dy;
while (curNode.next != null) {
if (curNode.next.val == val) {
curNode.next = curNode.next.next;
} else {
curNode = curNode.next;
}
}
return dy.next;
}
2.設(shè)計(jì)鏈表
在鏈表類中實(shí)現(xiàn)這些功能：
1. get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值捶惜。如果索引無效鸽心，則返回-1瞒滴。
2. addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)姨夹。插入后夸溶，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
3. addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素剧辐。
4. addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)寒亥。如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾荧关。如果 index 大于鏈表長度溉奕，則不會(huì)插入節(jié)點(diǎn)。如果index小于0忍啤，則在頭部插入節(jié)點(diǎn)加勤。
5. deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)同波。
class MyLinkedList {
ListNode head = null;
/**
* Initialize your data structure here.
*/
public MyLinkedList() {
}
/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
*/
public int get(int index) {
if (head == null) {
return -1;
} else {
ListNode node = head;
for (int i = 0; i < index; i++) {
node = node.next;
if (node == null) {
return -1;
}
}
return node.val;
}
}
public ListNode getNode(int index) {
if (head == null) {
return head;
} else {
ListNode node = head;
for (int i = 0; i < index; i++) {
node = node.next;
if (node == null) {
return node;
}
}
return node;
}
}
/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
*/
public void addAtHead(int val) {
if (head == null) {
head = new ListNode(val);
} else {
ListNode node = new ListNode(val);
node.next = head;
head = node;
}
}
/**
* Append a node of value val to the last element of the linked list.
*/
public void addAtTail(int val) {
if (head == null) {
head = new ListNode(val);
} else {
ListNode node = head;
while (node.next != null) {
node = node.next;
}
node.next = new ListNode(val);
}
}
/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
if (index <= 0) {
addAtHead(val);
} else {
ListNode preNode = getNode(index - 1);
ListNode nextNode = getNode(index);
ListNode culNode = new ListNode(val);
preNode.next = culNode;
culNode.next = nextNode;
}
}
/**
* Delete the index-th node in the linked list, if the index is valid.
*/
public void deleteAtIndex(int index) {
if (index == 0) {
head = head.next;
} else {
ListNode node = getNode(index - 1);
if (node != null && node.next != null) {
node.next = node.next.next;
}
}
}
}
3.反轉(zhuǎn)鏈表
題意：反轉(zhuǎn)一個(gè)單鏈表鳄梅。
示例: 輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
迭代實(shí)現(xiàn)
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode culNode = head;
ListNode preNode = null;
while (culNode != null) {
ListNode nextNode = culNode.next;
culNode.next = preNode;
preNode = culNode;
culNode = nextNode;
}
return preNode;
}
遞歸實(shí)現(xiàn)
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
public ListNode reverse(ListNode pre, ListNode cul) {
if (cul == null) {
return pre;
}
ListNode next = cul.next;
cul.next = pre;
return reverse(cul, next);
}
4.環(huán)形鏈表II
題意：給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)未檩。 如果鏈表無環(huán)戴尸，則返回 null。
為了表示給定鏈表中的環(huán)冤狡，使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）孙蒙。
如果 pos 是 -1项棠，則在該鏈表中沒有環(huán)。
「說明」：不允許修改給定的鏈表挎峦。
//用set
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> set = new HashSet();
while (head != null) {
if (!set.add(head)) {
return head;
}
head = head.next;
}
return null;
}
//快慢指針
public ListNode detectCycle2(ListNode head) {
ListNode fastIndex = head;
ListNode slowIndex = head;
while (fastIndex != null && fastIndex.next != null) {
fastIndex = fastIndex.next.next;
slowIndex = slowIndex.next;
if (fastIndex == slowIndex) {
fastIndex = head;
while (fastIndex != slowIndex) {
fastIndex = fastIndex.next;
slowIndex = slowIndex.next;
}
return fastIndex;
}
}
return null;
}
