# 【数据结构】链表练习题

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
while(pre != null && pre.next != null){
if(pre.next.val == val){
pre.next = pre.next.next;
}else{
pre = pre.next;
}
}
return dummy.next;
}
}
``````

1. 链表的中间结点

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
// 快慢指针：
class Solution {
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
//普通方法：
class Solution {
int len = 0;
while(cur != null){
cur = cur.next;
len++;
}
int len2 = len/2;
for(int i = 0; i < len2; i++){
cur = cur.next;
}
return cur;
}
}
``````

2. 链表中倒数第K个节点

``````/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int i = 0;
while(fast != null){
fast = fast.next;
if(i >= k){
slow = slow.next;
}
i++;
}
if(i < k){
return null;
}

return slow;
}
}
``````

3. 链表分割

``````import java.util.*;

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
}
ListNode bStart = new ListNode(-1);
ListNode bEnd = bStart;
ListNode aStart = new ListNode(-1);
ListNode aEnd = aStart;
while(cur != null){
if(cur.val < x){
bEnd.next =  new ListNode(cur.val);
bEnd = bEnd.next;
}else{
aEnd.next = new ListNode(cur.val);
aEnd = aEnd.next;
}
cur = cur.next;
}
bEnd.next = aStart.next;
return bStart.next;
}
}
``````

4. 翻转链表(迭代与递归两种方法)

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
}
public static ListNode reverse(ListNode prev,ListNode cur) {
if(cur == null){
return prev;
}
ListNode curNext = cur.next;
cur.next = prev;
return reverse(cur,curNext);
}

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

*** 5. 删除链表中的相同元素

``````/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
}
while(cur != null){
if(cur.next != null && cur.val == cur.next.val){
while (cur.next != null && cur.val == cur.next.val){
cur = cur.next;
}
cur = cur.next;
}else{
cur = cur.next;
}
}
}
}
``````

6. 链表的回文结构

``````import java.util.*;

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
//如果链表为空，直接反回true，如果链表只有一个节点，直接返回true
if (A == null){
return false;
}else if (A.next == null){
return true;
}
ListNode slow = A;
ListNode fast = A;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}

ListNode p = slow.next;
ListNode p1 = p.next;
//将后半部分的链表逆置
while (p != null){
p.next = slow;
slow = p;
p = p1;
if (p1 != null) {
p1 = p1.next;
}
}
while(slow != A) {
if (slow.val != A.val){
return false;
}
//偶数节点
if (A.next == slow){
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}
``````

7. 判断链表是否有环

``````/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
``````

8. 返回环起始位置

``````/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
``````

9.相交链表

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
return null;
}
if (alen < blen) {
for (int i = 0; i < blen - alen; i++) {
}
} else {
for (int i = 0; i < alen - blen; i++) {
}
}
}
}

public static int getLength(ListNode tmp) {
int cnt = 0;
while (tmp != null) {
cnt++;
tmp = tmp.next;
}
return cnt;
}
}
``````

10.合并两个有序链表

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
return null;
}
if (alen < blen) {
for (int i = 0; i < blen - alen; i++) {
}
} else {
for (int i = 0; i < alen - blen; i++) {
}
}
}
}

public static int getLength(ListNode tmp) {
int cnt = 0;
while (tmp != null) {
cnt++;
tmp = tmp.next;
}
return cnt;
}
}
``````