# LeetCode 链表题 ( Java )

## leetcode 237. 删除链表中的节点

```输入: head = [4,5,1,9], node = 5

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
```

## leetcode 160. 相交链表

```public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null)
return null;

int lengthA = getListLength(headA);
int lengthB = getListLength(headB);
ListNode longList = headA;
ListNode shortList = headB;
int offset = Math.abs(lengthA - lengthB);
if(lengthA < lengthB){
}
for(int i=0; i < offset; i++){
longList = longList.next;
}
while(shortList != longList){
shortList = shortList.next;
longList = longList.next;
}
return shortList;
}
public int getListLength(ListNode p){
int length = 0;
while(p != null){
length++;
p = p.next;
}
return length;
}
}
```

```public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
```

## leetcode 206. 反转链表

```输入: 1->2->3->4->5->NULL

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null) {
ListNode next = head.next;
head.next = prev;           // 翻转

}
return prev;
}
}
```

## leetcode 141. 环形链表

```输入：head = [3,2,0,-4], pos = 1

```输入：head = [1], pos = -1

#### （1） 哈希

```public boolean hasCycle(ListNode head) {
Set<ListNode> nodes = new HashSet<>();
while (head != null) {
return true;
} else {
}
}
return false;
}
```

#### （2）双指针

```public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null) {
if (slow == fast){
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
```

## leetcode 19. 删除链表的倒数第N个节点

```给定一个链表: 1->2->3->4->5, 和 n = 2.

（1）第一种方法：由于不清楚链表的长度，因此可以先遍历链表得到其长度，然后第二次遍历将倒数第N个节点删除，即被删除节点的前一个节点指向删除节点的后一个节点：

```public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
int length  = 0;
ListNode list = head;
while (list != null) {
length++;
list = list.next;
}
length -= n;
list = dummy;
while (length > 0) {
length--;
list = list.next;
}
list.next = list.next.next;
return dummy.next;
}
```

（2）第二种方法：使用双指针，先让其中一个指针走 N+1 步，然后两个指针同时移动，到达被删除节点的前一个节点时把它删除：

```public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
ListNode q = dummy;
for (int i = 0; i <= n; i++) {
q = q.next;
}
while (q != null) {
p = p.next;
q = q.next;
}
p.next = p.next.next;
return dummy.next;
}
```