【数据结构】【链表专题】链表常用的编程技巧

举报
huahua.Dr 发表于 2022/09/05 23:05:00 2022/09/05
【摘要】 ​必备知识链表是一种兼具递归和迭代性质的数据结构,常用技巧:双指针中的快慢指针。一、合并两个有序链表(虚拟头结点)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(in...

必备知识

链表是一种兼具递归和迭代性质的数据结构,常用技巧:双指针中的快慢指针。

一、合并两个有序链表(虚拟头结点)

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode mergeTwoLists(ListNod

e list1, ListNode list2) {

        ListNode result = new ListNode();// 使用虚拟头结点:第一个节点为空,从第二个节点开始才是想要的

        ListNode p = result;

        ListNode p1 = list1,p2 = list2;

        while(p1 != null && p2!=null) {

            if(p1.val > p2.val) {

                p.next = p2;

                p2 = p2.next;

            } else {

                p.next = p1;

                p1 = p1.next;

            }

            p = p.next;

        }

        while(p1 != null) {

            p.next = p1;

            p1 = p1.next;

            p = p.next;

        }

        while (p2 != null) {

            p.next = p2;

            p2= p2.next;

            p = p.next;

        }

        return result.next;

    }

}

思路:

合并两个单链表:

1.使用双指针循环遍历,两个单链表同时遍历比较;然后移动指针

2.两个单链表同时遍历完后,最多会剩下一个单链表还有值,需要将剩下的也合并。

3.两个单链表都需要判断一下是否为空,不空就合并,最后返回合并后的链表

4.可以使用虚拟头结点进行辅助

二、合并K个有序链表(虚拟头结点和二叉堆)

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        ListNode result = new ListNode();

        ListNode temp = result;

        if(lists.length == 0) {

            return null;

        }

        PriorityQueue<ListNode> minHead = new PriorityQueue<>(lists.length, Comparator.comparingInt(o -> o.val));

        for (ListNode node: lists

             ) {

            if (node != null){

                minHead.offer(node);

            }

        }

        while (!minHead.isEmpty()) {

            ListNode node = minHead.poll();

            temp.next = node;

            if (node.next != null) {

                minHead.offer(node.next);

            }

            temp = temp.next;

        }

        return result.next;

    }

}


思路:

  1. 分析题目,合并K个有序的链表,则需要找出这K个链表中最小的那个节点,使用优先队列-二叉堆-最小堆得特性,辅助
  2. 创建一个虚机头结点的结果链表
  3. 遍历将K个链表先放进优先队列中,因为是有序的,则第一批放进去的肯定存在最小的节点
  4. 再一个个出队列,第一个出队的就是最小,将最小的节点放到结果链表中,然后再将最小节点的下一个节点放进优先队列中进行排序
  5. 最后将一个个出队,放到结果链表,返回即可。


三、删除链表中倒数第N个结点(同步双指针)

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode result = new ListNode(-1);

        ListNode dump = result;

        ListNode p1 = head;

        for(int i =0; i< n; i++) {

           p1 = p1.next;

        }

        ListNode p2 = head;

        while(p1 != null) {

            result.next = p2;

            p2 = p2.next;

            result = result.next;

            p1 = p1.next;                      

        }

        result.next = p2.next;

        return dump.next;

    }

}

寻找第k个节点思路:使用双指针

// 返回链表的倒数第 k 个节点

ListNode findFromEnd(ListNode head, int k) {

    ListNode p1 = head;

    // p1 先走 k 步

    for (int i = 0; i < k; i++) {

        p1 = p1.next;

    }

    ListNode p2 = head;

    // p1 和 p2 同时走 n - k 步

    while (p1 != null) {

        p2 = p2.next;

        p1 = p1.next;

    }

    // p2 现在指向第 n - k 个节点

    return p2;

}

四、返回链表中的中间结点(快慢双指针)

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode middleNode(ListNode head) {

        ListNode show = head;

        ListNode fast = head;

        while(show !=null && fast !=null && fast.next !=null) {

            show = show.next;

            fast = fast.next.next;

        }

        return show;

    }

}


  思路:

  如果知道链表的长度N,即可返回其中间结点了,问题在于长度N未知,如何一次遍历寻找其长度。

使用快慢指针,快指针每次走两步,慢指针每次走一步,快慢刚好相差两倍,当快指针走到最后时,慢指针刚好走到中间


五、有环的链表

1.判断链表是否有环(使用快慢双指针)

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode fast = head;

        ListNode show = head;

        while (show != null && fast != null && fast.next != null) {

            fast = fast.next.next;

            show = show.next;

            if (fast == show) {

                return true;

            }

        }

        return false;

    }

}

思路:

使用快慢双指针,如果有环,则快慢指针一定相遇(即相等)则是有环,如果最后是null则没有环


2.返回有环链表的起点(先使用快慢双指针找到环,再使用同步双指针找到相遇点)

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;

        ListNode show = head;

        while(show != null && fast !=null && fast.next != null) {

            show = show.next;

            fast = fast.next.next;

            if (show == fast) {

                break;

            }

        }

        if(fast == null || fast.next == null) {

            return null;

        }

        show = head;

        while(show != fast) {

            show = show.next;

            fast = fast.next;

        }

        return show;

    }

}

思路:

1.先使用快指针找到是否有环,并知道所在环的路径

2.然后快指针在成环的位置上,慢指针在起点,同时移动指针,如果再次相遇即是,入环的第一个起点了


六、相交链表

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode one = headA;

        ListNode two = headB;

        while (one != two) {

            if (one == null) {

                one = headB;

            } else {

                one = one.next;

            }

            if(two == null) {

                two = headA;

            } else {

                two = two.next;

            }

        }

        return one;

    }

}

思路:

两条链表同时遍历,A遍历完就接着遍历B,B遍历完就接着遍历A,由于最后遍历的次数是相同,如果遇到相同节点,就是相交的节点,如果没有相交,则最后都是null.


七、反转链表


1.反转全链表

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode reverseList(ListNode head) {

        if(head == null || head.next == null) {

            return head;

        }

        ListNode last = reverseList(head.next);

        head.next.next = head;

        head.next = null;

        return last;

    }

}

思路:

利用递归,后序遍历,将相邻的两个节点的指针给换位置即可。


2.反转前N个结点

Class Solusion {

ListNode rear = null;

Public ListNode reverseListN(ListNode head, int n) {

If (n == 1) {

rear = head.next;

}

ListNode last = reverseListN(head.next, n-1);

head.next.next = head;

head.next = rear;

}

return last;

}
  • 反转区间结点的链表
/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    ListNode rear = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == 1) {

            return reverseListN(head, right);

        }

        head.next = reverseBetween(head.next,left-1,right-1);

        return head;

    }

    ListNode reverseListN(ListNode head, int n) {

        if (n == 1) {

            rear = head.next;

            return head;

        }

        ListNode last = reverseListN(head.next, n-1);

        head.next.next = head;

        head.next = rear;

    return last;

    }

}

     思路:

           1.现将区间和链表同时移动,直到是从1开始反转,也就是只反转前几个节点就可以了

           2.调用反转前N个结点的递归方法即可

  • k个一组反转链表
/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {

        if(head == null) {

            return null;

        }

        ListNode a = head;

        ListNode b = head;

        for(int i = 0; i< k; i++) {

            if(b == null) {

                return head;

            }

            b = b.next;

        }

        ListNode temp = reverse(a,b);

        a.next = reverseKGroup(b,k);

        return temp;

    }

     ListNode reverse(ListNode a, ListNode b) {

        ListNode pre = null;

        ListNode cur = a;

        ListNode next = a;

        while(cur != b) {

            next =cur.next;

            cur.next = pre;

            pre  = cur;

            cur = next;

        }

        return pre;

    }

}

思路:使用迭代性质,前序遍历

  1. 先反转head开头的第k个结点
  2. 接着反转第k+1个元素为head递归调用reverseKGroup函数
  3. 最后将反转的结果接上即可。

八、判断回文单链表;

方法1:将原链表反转成一条新链表保存起来,然后两条链表同时比较即可判断是否是回文链表

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    ListNode newHead = new ListNode(-1);

    public boolean isPalindrome(ListNode head) {

        ListNode p2 = newHead;

        ListNode p3 = reverse(head);

        p2 = p2.next;

        while(p2 != null) {

            if(p2.val != p3.val) {

                return false;

            }

            p2 = p2.next;

            p3 = p3.next;

        }

        return true;

    }

    ListNode reverse(ListNode head) {

        newHead.next = new ListNode(head.val);

        newHead = newHead.next;

        if (head == null || head.next == null) {

            return head;

        }

        ListNode last = reverse(head.next);

        head.next.next = head;

        head.next = null;

        return last;

    }

}


方法2:使用二叉树的后序遍历

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    ListNode left = null;

    boolean flag = true;

    public boolean isPalindrome(ListNode head) {

        left = head;

        df(head);

        return flag;

    }

    void df(ListNode right) {

        if(right == null) {

            return;

        }

        df(right.next);

        if(left.val != right.val) {

            flag = false;

        }

        left = left.next;

    }

}

方法3:先找到中点,取中点前面部分保存,然后翻转后面部分,保存,最后两部分进行比较即可(利用类似二分法的方式)

九、使用快慢指针-删除链表中重复元素

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if(head == null) {

            return head;

        }

        ListNode show = head;

        ListNode fast = head.next;

        while(fast != null) {

            if(show.val == fast.val) {

                fast = fast.next;

                continue;

            }

            show.next = fast;

            fast = fast.next;

            show = show.next;

        }

        show.next = null;

        return head;

    }

}

思路:

1.使用快慢双指针

2.慢指针与快指针相比较,快指针在前面探路,如果快慢指针的值不相等,则将慢指针的位置值替换成快指针的,然后双方继续前进一步

3.最后将慢指针的next置为null并返回头链表


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。