# 【Java数据结构】你必须要掌握的链表面试经典例题（附超详细图解和代码）

1，反转一个单链表

3，输入一个链表，输出该链表中倒数第k个结点

4，删除链表中的多个重复值

5，链表的回文结构

6，合并两个链表

7，输入两个链表，找出它们的第一个公共结点。

8，判断一个链表是否有环

9，求有环链表的环第一个结点

# 二，链表经典例题

## 1，反转一个单链表

``````public ListNode reverseList() {
return null;
}
ListNode prev = null;

while (cur != null) {
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}``````

``````public ListNode middleNode() {
return null;
}
while(fast != null && fast.next != null){
fast = fast.next.next;
if(fast == null) {
return slow;
}
slow = slow.next;
}
return slow;
}``````

## 3，输入一个链表，输出该链表中倒数第k个结点

`````` public ListNode findKthToTail(int k) {
if(k <= 0 || head == null) {
return null;
}
while (k-1 != 0) {
fast = fast.next;
if(fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}``````

## 4，删除链表中的多个重复值

``````//删除所有值为key的节点
public ListNode removeAllKey(int key){
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//最后处理头
}
}
``````

## 5，链表的回文结构

`````` public boolean chkPalindrome(ListNode A) {
// write code here
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow走到了中间位置-》反转

ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//反转完成
return false;
}
return true;
}
slow = slow.next;
}
return true;
}``````

## 6，合并两个链表

``````public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
tmp = tmp.next;
}else {
tmp = tmp.next;
}
}
}
}
}``````

## 7，输入两个链表，找出它们的第一个公共结点。

`````` public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
return null;
}

int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null
int len = lenA-lenB;//差值步
if(len < 0) {
len = lenB-lenA;
}
//1、pl永远指向了最长的链表   ps 永远指向了最短的链表  2、求到了差值len步

//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同时走 直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}``````

## 8，判断一个链表是否有环

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

## 9，求有环链表的环第一个结点

`````` public ListNode detectCycle(ListNode head) {
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}``````

THE END

)">