【数据结构】环形、相交、回文、分割、合并、反转链表

椰椰椰耶

发布于 2024-10-15 15:22:52

2030

文章被收录于专栏：学习学习

反转链表

206. 反转链表 - 力扣（LeetCode）

思路解透

本题就是通过不停地将最先的 head 节点位置的后一位插到最前面，完成链表的反转本题需要两个节点变量

cur：其任务就是定位到原 head 节点位置的前一位，然后将自己插入到当前 head 节点的前面
- 因为链表的最后一个节点都是指向一个 null 值，所以需要将最先的 head 节点的 next 置为空
- 但在将 head.next 置为 null 之前，需要先将 cur 节点实例化出来，不然 cur 就无法找到原先的 head 节点的位置了
curN：其任务就是定位到 cur 的后一个节点，方便让 cur 进行循环插入
- 其在循环中进行实例化，因为每一次插入完成之后，curN 的位置都是需要随着 cur 的改变而改变
- curN 实例化为 cur 的下一个节点。在 cur 插入完成后，cur 就会定位到 curN 的位置，若此为止不为 null，则继续进行前插

代码解析

class Solution {
    public ListNode reverseList(ListNode head) {
        //1. 防止空指针异常  
		if(head == null){  
    		return head;  	
		}  
		  
		//2. 将head.next置为空  
		//注意先把 cur 节点给先弄出来  
		ListNode cur = head.next;  
		head.next = null;  
		  
		//3. 进行循环头插  
		while (cur != null) {  
		    ListNode curN = cur.next;  
		    cur.next = head;  
		    head = cur;  
		    cur = curN;  
		}  
		return head;
	}
}

寻找中间节点

876. 链表的中间结点 - 力扣（LeetCode）

思路解透

解法 1：定义一个 cur 节点，从 head 节点的地方，向后走 size()/2 步，就到了中间位置解法 2：定义一个 slow 节点，一次走一步，在定义一个 fast 节点，一次走两步，当 fast 走完的时候，slow 就刚好在中间位置（快慢指针）

当有偶数个节点时，循环判断条件为：fast != null
当有奇数个节点时，循环判断条件为：fast.next != null
这里的两个条件判断顺序不能换，否则会报空指针异常错误

快慢指针原理：路程一样的情况下，速度是两倍，那么当走完的时候，路程也是两倍

代码解析（法 1）

public ListNode middleNode(){  
    int count = 0;  
    ListNode node = head;  
    while(node != null){  
        count++;  
        node = node.next;  
    }    
    ListNode cur = head;  
    for (int i = 0; i < count/2; i++) {  
        cur = cur.next;  
    }    
    return cur;  
}

代码解析（法 2）

public ListNode middleNode(){  
    ListNode slow = head;  
    ListNode fast = head;  
    while(fast != null && fast.next != null){  
    	//slow走一步，fast走两步
        slow = slow.next;  
        fast = fast.next.next;  
    }    
    return slow;  
}

返回链表中倒数第 k 个节点

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

思路解透

首先判断 k 是否合法，链表是否为为 null
1. k <= 0，返回-1
2. （下面的第二点看完再回来）因为如果 k 大于链表长度的话，当 fast 走 k - 1 步的时候就会走出链表，所以在 fast 走 k-1 步的过程中如果出现 fast == null，则返回 -1
定义两个节点，fast 先走 k - 1 步，随后 fast 和 slow 一起走，当 fast 走到最后了，slow 所在的地方就是倒数第 k 个节点

代码解析

public int kthToLast(int k) {  
	//判断k是否合法，链表是否为null
    if(k <= 0 || head == null) {  
        return -1;  
    }    
    ListNode fast = head;  
    ListNode slow = head;  
    int count = 0;  
    while (count != k - 1) {  
        //fast先向后走k-1步        
        fast = fast.next;  
        if(fast == null){
        //判断k是否合法
            return -1;  
        }
        count++;  
    }    
    while (fast.next != null){
    	//两个节点一起向后走，直到fast走到最后一个  
        fast = fast.next;  
        slow = slow.next;  
    }    
    return slow.val;  
}

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路解透

创建一个新的链表，为虚拟节点（傀儡节点），然后对需要合并的两个链表中的值进行比较，谁小谁就接在虚拟节点后面

创建一个新的节点 newH，在这个链表上进行合并，再创建一个 tmp 节点，用来指向 newH 链表中的最后一个节点
当 headA != null && headB != null 的时候，进行比较
1. 若 headA. val < headB. val，则将 headA 这个节点接在 newH 后面，即接在 tmp 节点后面，最后 tmp 和 headB 节点均向后移一位
2. 若 headA. val > headB. val，则将 headB 这个节点接在 newH 后面，即接在 tmp 节点后面，最后 tmp 和 headB 节点均向后移一位
当 headA == null || headB == null 的时候，剩下的一个链表里面的节点直接接到 newH 后面就行了
最后返回 newH. next，因为 newH 是一个虚拟节点，不存在于要合并的链表中，它只是一个引子

代码解析

public ListNode mergeTwoLists(ListNode headA, ListNode headB) {  
    ListNode newH = new ListNode(0);  
    ListNode tmp = newH;  
    while(headA != null && headB != null){  
        if(headA.val < headB.val){  
        	//将headA接到newH上面，随后后移
            tmp.next = headA;  
            headA = headA.next;  
            tmp = tmp.next;  
        }else if{  
        	//将headB接到newH上面，随后后移
            tmp.next = headB;  
            headB = headB.next;  
            tmp = tmp.next;  
        }    
    }    
    if(headA == null){  
    	//headA空了，将headB直接接到newH后面
        tmp.next = headB;  
    }    
    //headB空了，将headA直接接到newH后面
    if (headB == null) {  
        tmp.next = headA;  
    }    
    return newH.next;  
}

分割链表

链表分割_牛客题霸_牛客网 (nowcoder.com)

思路解透

构建两个区间，一个里面接上小于 x 的节点，一个里面接上大于 x 的节点，最后将这两个区间连接起来

若链表为空
遍历链表
- 创建一个 cur 节点，用来遍历链表
把对应的节点放到指定区间
1. 在小区间里
  1. 创建 bs（before start）节点指向区间里面最前面的一个节点，创建 be（before end）节点指向区间里面最后一个节点
  2. 在小区间里面插入第一个节点的时候，bs 和 be 都指向这个节点，随后 cur 向后移
  3. 之后插入的节点均为尾插，bs 位置不变，be 始终指向新插入的节点
2. 在大区间里
  1. 创建 as（after start）节点指向区间里面最前面的一个节点，创建 ae（after end）节点指向区间里面最后一个节点
  2. 在小区间里面插入第一个节点的时候，as 和 ae 都指向这个节点，随后 cur 向后移
  3. 之后插入的节点均为尾插，as 位置不变，ae 始终指向新插入的节点
把两个区间连接起来
1. 将 be 节点和 as 节点连接起来，并且将 ae 节点的 next 置为 null，作为新链表的尾巴，并且返回 bs 节点
2. 若所有节点全在小区间里，就将 be 节点的 next 置为 null，作为新链表的尾巴，并且返回 bs 节点
3. 若全在大区间里，则返回 ae 节点

代码解析

public ListNode partition(ListNode pHead, int x) {  
    //判断空链表
    if(pHead == null){  
        return null;  
    }      
    //小区间的两个节点
    ListNode bs = null;  
    ListNode be = null;  
    //大区间的两个节点
    ListNode as = null;  
    ListNode ae = null;  
	
	//遍历链表的节点
    ListNode cur = pHead;  
    while(cur != null){  
    	//插入小区间
        if(cur.val < x){  
        	//第一次插入
            if(bs == null){  
                bs = be = cur;  
            }else{  
                be.next = cur;  
                be = be.next;  
            } 
        //插入大区间       
        }else{  
        	//第一次插入
            if(as == null){  
                as = ae = cur;  
            }else{  
                ae.next = cur;  
                ae = ae.next;  
            }        
        }        
    cur = cur.next;  
    }    
    //当节点全部都在小区间时，直接返回大区间
    if(bs == null){  
        return as;  
    }    
    
    //进行大小区间的拼接
    be.next = as;  
    //大区间不为空，把最后一个节点置空，作为尾巴
    if(as != null){  
        ae.next = null;  
    }  
    return bs;  
}

回文链表

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

思路解透

首先用快慢指针找到中间的节点（上面第二题有讲解）
再对后半部分进行反转（上面第一题有讲解）
最后让首尾两个节点往中间走，直到相遇，返回 true；若是偶数个节点，则只需要前面节点的 next 与后面节点的值相等即可返回 true

代码解析

public boolean chkPalindrome(ListNode head) {  
    // write code here  
    if (head == null) {  
        return true;  
    }  
    //1. 找到链表的中间节点  
    ListNode fast = head;  
    ListNode slow = head;  
  
    while (fast != null && fast.next != null) {  
        slow = slow.next;  
        fast = fast.next.next;  
    }  
    //2. 反转后半节点  
    ListNode cur = slow.next;  
    slow.next = null;  
    while (cur != null) {  
        ListNode curN = cur.next;  
        cur.next = slow;  
        slow = cur;  
        cur = curN;  
    }  
    //3. slow从后往前，head从前往后，直到相遇  
    while (head != slow) {  
        if (head.val != slow.val) {  
            return false;  
        }        
        //当节点个数为偶数
        if (head.next == slow)  
            return true;  
        head = head.next;  
        slow = slow.next;  
    }    
    return true;  
}

相交链表

160. 相交链表 - 力扣（LeetCode）

思路解透

首先计算两个链表的长度，并计算他们的差值
随后让长的链表的头节点先走“差值“步，让他们站在同一起跑线
最后让他们携手同行，直到相遇，返回任意一个链表；若最终零个引用都为空，证明不相交，返回 null

代码解析

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
    //1. 计算两个链表的长度，并计算差值  
    int lenA = 0;  
    int lenB = 0;  
    ListNode curA = headA;  
    ListNode curB = headB;  
    while (curA != null) {  
        curA = curA.next;  
        lenA++;  
    }    
    while (curB != null) {  
        curB = curB.next;  
        lenB++;  
    }    
    int len = lenA - lenB;  
  
    curA = headA;  
    curB = headB;  
  
    //2. 根据差值，长的链表头节点先走len步，  
    // 让两个链表在同一起跑线  
    if (len > 0) {  
        int count = 0;  
        while (count != len) {  
            curA = curA.next;  
            count++;  
        }    
    } else {  
        int count = 0;  
        while (count != -len) {  
            curB = curB.next;  
            count++;  
        }    
    }  
    //3. 两个链表的节点携手同行，直到相等  
    while (curA != curB) {  
        curA = curA.next;  
        curB = curB.next;  
    }    
    if (curA == null) {  
        //若两个引用都为空，证明不相交  
        return null;  
    }    
    return curA;  
}

环形链表

141. 环形链表 - 力扣（LeetCode）

思路解透

定义两个节点，一个一次走一步，一个一次走两步
当走得快的节点不为空，并且走得快的节点的 next 不为空，循环就一直继续
当两个节点相等，则返回 true

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

代码解析

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

环形链表Ⅱ

142. 环形链表 II - 力扣（LeetCode）

思路解透

代码解析

public ListNode detectCycle(ListNode head) {  
    //1. 判断是否有环  
    ListNode fast = head;  
    ListNode slow = head;  
    while (fast != null && fast.next != null) {  
        fast = fast.next.next;  
        slow = slow.next;  
        //有环，跳出循环  
        if (fast == slow) {  
            break;  
        }    
    }    
    //若是因为没有环而跳出循环的话，返回null  
    if (fast == null || fast.next == null) {  
        return null;  
    }    
    //此时slow在相遇点，将fast拿到起始点  
    //让他们相向而行，相遇点即为入口点  
    fast = head;  
    while(fast != slow) {  
        fast = fast.next;  
        slow = slow.next;  
    }    
    return fast;  
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-02，如有侵权请联系 cloudcommunity@tencent.com 删除

链表