链表常见面试题( 建议收藏！！)

1.删除链表中等于给定值 val 的所有节点

题目： 在线OJ

思考：
①用 tmp 记录当前节点，若 tmp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除 tmp 的下一个节点—— tmp.next = tmp.next.next
②若 tmp 的下一节点值不等于 val，则保留下一个节点，并把 tmp 移到下一节点
③当 tmp 的下一节点为空时，链表遍历结束，此时所有节点值为 val 的节点都被删除

代码实现：

public Node deleteAllVal(Node head,int val){	//考虑head为空的情况	if(head == null){		return null;	}	//tmp表示当前节点	Node tmp = head;	//cur表示待删除节点	Node cur = head.next;	while(cur != null){		if(tmp.data == val){			tmp.next = cur.next;			cur = cur.next;		}		else{			tmp = cur;			cur = cur.next;		}	}	if(head.data == val){		head = head.next;	}	return head;}

2.反转一个单链表?

题目： 在线OJ

思考：
.

方法1 迭代

• 用 cur 表示当前需要反转的节点
• 创建一个 prev，初始化为null，指向cur
• curNext 表示下一个需要反转的节点
• 当 cur 为空的时候，表示链表遍历结束 (循环结束条件)
• 最后返回 newHead

public Node reverseList(Node head){    Node prev = null;    Node cur = this.head;    Node newHead = null;    while (cur != null){        Node curNext = cur.next;        if(curNext == null){            newHead = cur;        }        cur.next = prev;        prev = cur;        cur = curNext;    }    return newHead;}

反转结束后，不能再使用原来得 print 方法进行打印，因为它是从原来得 head 开始，而此时是 newHead，则需要重写一个 newPrint 方法

新得 print 方法：

public static void newPrint(Node newHead){    Node cur = newHead;    while (cur != null){        System.out.print(cur.data+" ");        cur = cur.next; //节点后移    }    System.out.println();}

方法2 利用头插法

• 先将头节点的 next 域置为null
• 将head之后的一个节点进行头插法
• 以此类推，直到最后一个节点头插结束后，则反转完毕

public Node reverseList2(){    if(this.head == null) {        return null;    }    if(this.head.next == null) {        return this.head;    }    Node cur = this.head.next;    this.head.next = null;    while (cur != null) {        Node curNext = cur.next;        this.addFist(cur.data);        cur = curNext;    }    return this.head;}

3.链表的中间节点

题目： 在线OJ

要求： 给定一个头结点为 head 的非空单链表，返回链表的中间结点；如果有两个中间结点，则返回第二个中间结点
.
即：

思考：

1. 定义一个两个指针 fast、slow
2. slow 一次走一个节点，fast 一次走两个节点
3. 当 fast 走完，即 fast.nest / fast 为 null 时，slow刚好指向 “中间节点”

核心： fast 的速度是 slow 的二倍

代码实现：

public Node middleNode(){    Node fast = this.head;    Node slow = this.head;    while(fast != null && fast.next != null){         slow = slow.next;        fast = fast.next.next;    }    return slow;}

4.链表中倒数第k个节点

题目： 在线OJ

思考：

• 创建两个指针fast、slow，均指向 head节点
• 让 fast 走 k-1步
• 然后slow 和 fast一起，一次走一步
• 当 fast 走完时，即 fast.nest 为 null 时，slow就指向倒数第k个节点

注意 k 的合法性判定

代码实现：

public Node getKthFromEnd(int k) {    //k 合法性判定    if(k <= 0){        System.out.println("k不合法！");        return null;    }    Node fast = this.head;    Node slow = this.head;    while(k-1 > 0){        if(fast.next != null){            fast = fast.next;            k--;        }        else {            System.out.println("该节点不存在！");            return null;        }    }    while(fast.next != null){        fast = fast.next;        slow = slow.next;    }    return slow;}

5.链表分割

题目： 在线OJ

思考：

• 创建两个"线段"，两个线段的头 (bs、be) 尾 (as、ae) 均初始化为 null
• 定义 cur，遍历原来的单链表
• 若 cur.data < x，则放到第一个线段
  若 cur.data > x，则放到第二个线段
  均采用尾插法
• 当 cur 为 null 时，原来的单链表就遍历结束
• 最后将 be 和 as拼接，即：be.next = as

代码实现：

public Node partition(int x) {    Node bs = null;    Node be = null;    Node as = null;    Node ae = null;    Node cur = this.head;    while(cur != null){        if(cur.data < x){            //第一次插入            if(bs == null){                bs = cur;                be = cur;            }            else{                be.next = cur;                be = be.next;            }        }        else {            //第一次插入            if(as == null){                as = cur;                ae = cur;            }            else{                ae.next = cur;                ae = ae.next;            }        }        cur = cur.next;    }    // 判断 bs是否为空，若 bs==null，返回as    if(bs == null){        return as;    }    be.next = as;    //若 bs不为 null，需进行拼接    if(ae != null){        ae.next = null;    }    //若ae不为 null，ae的next需要置为null    return bs;}

6.删除排序链表中的重复元素

题目： 在线OJ

思考：定义一个虚拟节点来解决问题

• 首先定义一个虚拟节点newHead
• 使用 cur 遍历链表，比较 cur.data 和 cur.next.data 是否相等
• 不相等，则将 cur节点，放置虚拟节点后
• 最后返回 newHead.next 即可

代码实现：

public Node deleteDuplicates() {    //虚拟节点    Node newHead = new Node(-1);    Node cur = this.head;    Node tmp = newHead;    while(cur != null){        if(cur.next != null && cur.data == cur.next.data){            while(cur.next != null && cur.data == cur.next.data){                cur = cur.next;            }            cur = cur.next;        }        else {            tmp.next = cur;            tmp = tmp.next;            cur = cur.next;        }    }    tmp.next = null;    return newHead.next;}

最后记得手动将 tmp.next 置为 null，否则可能陷入死循环

7.回文链表?

题目： 在线OJ

思考：

• 先找到当前链表的中间节点
• 再反转单链表的后半部分
• 一个从头往后走，一个从尾往前走，依次比较

奇数个绩点节点
.

.
偶数个节点

代码实现：

public boolean isPalindrome() {    //单链表为null    if(this.head == null){        return false;    }    //只有一个节点    if(this.head.next == null){        return true;    }    //找单链表的中间节点  循环结束后 slow 即为中间节点    Node fast = this.head;    Node slow = this.head;    while(fast != null && fast.next != null){        fast = fast.next.next;        slow = slow.next;    }    //反转单链表的后半部分 slow 为中间节点    Node cur = slow.next;    while(cur != null){        Node curNext = cur.next;        cur.next = slow;        slow = cur;        cur = curNext;    }    //循环结束，slow 为最后一个节点    //一个从头，一个从尾    while(slow != this.head){        if(slow.data != this.head.data){            return false;        }        //偶数个节点        if(this.head.next == slow){            return true;        }        else{            slow = slow.next;            this.head = this.head.next;        }    }    return true;}

8.环形链表

题目： 在线OJ

思考：

• 定义 fast、slow
  fast一次走两步，slow一次走一步
• 若有环，则一定相遇
  若无环，则不相遇

每走一步，判断 slow 和 fast 是否相等，相等则有环
每走一步，都要进行判断 fast==null / fast.next ==null，若存在，则没有环

代码实现：

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

9.环形链表Ⅱ

题目： 在线OJ

思考分析： 即返回入环的地址
.

.

代码实现：

public Node detectCycle() {    Node fast = this.head;    Node slow = this.head;    //先找到相遇的点    while(fast != null && fast.next != null){        fast = fast.next.next;        slow = slow.next;        if(slow == fast){            break;        }    }    if(fast == null || fast.next == null){        return null;    }    slow = this.head;    while(slow != fast){        slow = slow.next;        fast = fast.next;    }    return slow;}

10.相交链表

题目： 在线OJ

思考分析：

• 首先要知道两个单链表的长度 lenA，lenB
• 计算两单链表长度的差值
• 让长的单链表先走 差值步
• 然后两个一起往后走，进行比较

代码实现：

public Node getIntersectionNode(Node headA,Node headB) {    //求长度，走差值步    int lenA = 0;    int lenB = 0;    Node pL = headA;    Node pS = headB;    while(pL != null){        lenA++;        pL = pL.next;    }    while(pS != null){        lenB++;        pS = pS.next;    }    pL = headA;    pS = headB;    int len = lenA - lenB;    //让pL指向长的    if(len < 0){        pL = headB;        pS = headA;        len = lenB - lenA;    }    //让pL先走len步    for (int i = 0; i < len; i++) {        pL = pL.next;    }    //pL pS一起走    while(pS != pL && pS != null && pL != null){        pS = pS.next;        pL = pL.next;    }    if(pL == pS && pL != null){        return pL;    }    return null;}

11.合并两个有序链表

题目： 在线OJ

思考分析：
.
最终结果：
.

过程：

• ①先比较 headA.data 和 headB.data 的大小，谁小谁先利用尾插法插入到虚拟节点后(以headA小为例)
• ②将headA后移，再进行比较，再将小的继续使用尾插法挪，以此类推

.

代码实现：

public Node mergeTwoLists(Node headA,Node headB) {    //虚拟节点    Node newHead = new Node(-1);    Node tmp = newHead;    while(headA != null && headB != null){        if(headA.data < headB.data){            tmp.next = headA;            tmp = tmp.next;            headA = headA.next;        }        else{            tmp.next = headB;            tmp = tmp.next;            headB = headB.next;        }    }    if(headA != null){        tmp.next = headA;    }    if(headB != null){        tmp.next = headB;    }    return newHead.next;}

欢迎大家一起探讨学习~