链表

2020-12-23 23:18:25
106
参与编辑
版本 1

链表

1 反转链表

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { if (head == null || head.next == null) retrun head; // 反转后链表 ListNode res = null; // 头结点的下一个节点 ListNode next = null; while (head != null) { // 将头节点的下一个节点取出 next = head.next; // 头结点后将反转的链表进行拼接 head.next = res; // 反转地址更新 res = head; // 头节点地址更新 head = next; } return res; } }

2 链表中k个节点一组进行翻转,最后不足k个的直接拼接

public class Solution { public ListNode reverseKGroup (ListNode head, int k) { // write code here if (head == null || head.next == null || k < 2) return head; ListNode res = new ListNode(-1); // 返回数据 res.next = head; int length = 0; // 链表长度 while (head != null) { length++; head = head.next; } ListNode pre = res; // 当前节点的上一个节点 ListNode cur = res.next; // 当前节点 ListNode next = null; for (int i = 0; i < length / k; i++) { // pre作为每一小段链表的头节点,负责衔接 for (int j = 1; j < k; j++) { next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } pre = cur; cur = cur.next; } return res.next; } }

3 链表内指定区间反转

public class Solution { public ListNode reverseBetween (ListNode head, int m, int n) { // write code here if (head == null || head.next == null) return head; ListNode res = new ListNode(-1); res.next = head; ListNode pre = res; for (int i = 1; i < m; i++) { pre = head; head = head.next; } ListNode temp = null; for (int i = 0; i < n - m; i++) { temp = head.next; head.next = temp.next; temp.next = pre.next; pre.next = temp; } return res.next; } }

4 判断一个链表是否是回文链表

public class Solution { /** * * @param head ListNode类 the head * @return bool布尔型 */ public boolean isPail (ListNode head) { // write code here // 快慢指针确定中间值,遍历过程中,前半段进行链表翻转 // 中间值确定后 从头和中间值开始进行遍历比较 if (head == null) return false; if (head.next == null) return true; ListNode left = head; ListNode right = head; ListNode res = null; ListNode temp = null; while (right != null && right.next != null) { // 快慢指针 left = left.next; right = right.next; if (right.next == null) break; right = right.next; // 翻转链表 temp = head.next; head.next = res; res = head; head = temp; } left = left.next; while (left != null) { if (res.val != left.val) return false; res = res.next; left = left.next; } return true; } }

5 两个链表生成相加链表

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 利用栈的先进后出特性
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        //往栈里面添加元素
        ListNode node1 = head1;
        ListNode node2 = head2;
        while (node1 != null) {
            stack1.push(node1.val);
            node1 = node1.next;
        }
        while (node2 != null) {
            stack2.push(node2.val);
            node2 = node2.next;
        }
        //开始相加
        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode tailer = head;
        while(!stack1.empty() || !stack2.empty() || carry != 0) {
            int a = 0;
            int b = 0;
            if (!stack1.empty()) {
                a = stack1.pop();
            }
            if (! stack2.empty()) {
                b = stack2.pop();
            }
            int sum = a + b + carry;
            int num = sum % 10;
            carry  = sum / 10;
            ListNode nodeNum = new ListNode(num);
            // 尾插法
            tailer.next = nodeNum;
            tailer = tailer.next;
        }
        head = head.next;
        // 反转后链表
        ListNode res = null;
        // 头结点的下一个节点
        ListNode next = null;
        while (head != null) {
            // 将头节点的下一个节点取出
            next = head.next;
            head.next = res;
            res = head;
            head = next;
        }
        return res;
    }
}

6 判断链表中是否有环

public class Solution { public boolean hasCycle(ListNode head) { // 快慢指针相遇说明有环 if (head == null || head.next == null) return false; 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; } }

7 链表中环的入口节点

思路:
1)同上一题,使用快慢指针方法,判定是否存在环,并记录两指针相遇位置(Z);

2)将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y)。

证明如下

如下图所示,X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置,则根据快指针速度为慢指针速度的两倍,可以得出:

2*(a + b) = a + b + n * (b + c);

a = (n - 1) * b + n * c;

a = (n - 1)(b + c) + c;

注意到b+c恰好为环的长度,故可以推出,如将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。

image.png

public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) return null; ListNode fast = head; ListNode slow = head; ListNode meetNode = null; // 先确定有环 while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { // 快慢指针相遇,说明有环 meetNode = fast; break; } } if (meetNode == null) return null; // 为空 没有相遇 返回null fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } }

8 查找两个链表是否有公共节点

public class Solution { // pHead1: 0-1-2-3-4-5-null // pHead2: a-b-4-5-null // 两个指针同时移动,移动到头 遍历对方的链接 时间复杂度O(n + m) // p1:0-1-2-3-4 -5-null-a-b-4-5-null // p2: a-b-4-5-null 0-1 -2-3-4-5-null public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null || pHead2 == null) return null; ListNode p1 = pHead1; ListNode p2 = pHead2; while (p1 != p2) { p1 = p1.next; p2 = p2.next; if (p1 != p2) { if (p1 == null) p1 = pHead2; if (p2 == null) p2 = pHead1; } } return p1; } }

9 合并有序链表

public class Solution { public ListNode mergeTwoLists (ListNode l1, ListNode l2) { // write code here ListNode head = new ListNode(0); ListNode next = head; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { next.next = l1; l1 = l1.next; } else { next.next = l2; l2 = l2.next; } next = next.next; } if (l1 != null) { next.next = l1; } if (l2 != null) { next.next = l2; } return head.next; } }

10 合并K个有序链表 O(logK)

public class Solution { // 知识点 1 分治,2 两个有序链表合并,2a 尾插法 public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists == null || lists.size() == 0) return null; return mergeKLists(lists, 0, lists.size() - 1); } private ListNode mergeKLists(ArrayList<ListNode> lists, int left, int right) { if (left >= right) { return lists.get(left); } int mid = left + (right - left) / 2; ListNode l1 = mergeKLists(lists, left, mid); ListNode l2 = mergeKLists(lists, mid + 1, right); return mergeTwoList(l1, l2); } private ListNode mergeTwoList(ListNode l1, ListNode l2) { ListNode head = new ListNode(-1); ListNode next = head; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { next.next = l1; l1 = l1.next; } else { next.next = l2; l2 = l2.next; } next = next.next; } if (l1 != null) { next.next = l1; } if (l2 != null) { next.next = l2; } return head.next; } }

11 单链表排序

public class Solution { // 知识点 1 快慢指针找中点,2 分治,3 合并有序链表,3a尾插法 public ListNode sortInList (ListNode head) { // write code here if (head == null || head.next == null) return head; ListNode fast = head.next; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode next = slow.next; slow.next = null; ListNode left = sortInList(head); ListNode right = sortInList(next); return mergeTwoList(left, right); } private ListNode mergeTwoList(ListNode left, ListNode right) { ListNode head = new ListNode(0); ListNode next = head; while (left != null && right != null) { if (left.val < right.val) { next.next = left; left = left.next; } else { next.next = right; right = right.next; } next = next.next; } next.next = left != null ? left : right; return head.next; } }

12 链表中倒数第k个节点

public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if (head == null || head.next == null) return head; ListNode left = head; ListNode right = head; for (int i = 0; i < k; i++) { if (right == null) return null; right = right.next; } while (right != null) { right = right.next; left = left.next; } return left; } }

13 删除链表倒数第n个节点

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode first = head;
        ListNode second = head;
        for (int i = 1; i < n; i++) {
            first = first.next;
        }
        ListNode pre = null;
        //first到尾节点, second到待删除节点
        while(first.next != null) {
            pre = second;
            second =  second.next;
            first = first.next;
        }
        //删除second节点
        if(pre != null) {
            pre.next = second.next;
        } else {
            //考虑删除头节点的情况
            head = head.next;
        }
        return head;
    }
}

14 ## 删除有序链表中重复的元素

public class Solution { public ListNode deleteDuplicates (ListNode head) { // write code here if (head == null || head.next == null) return head; ListNode res = new ListNode(-1); res.next = head; ListNode pre = res; ListNode right = head.next; ListNode temp = null; while (right!=null) { if (pre.next.val == right.val) { temp = pre; right = right.next; } else { if (temp != null) { pre.next = right; temp = null; } else { pre = pre.next; } right = right.next; } } if (temp != null) { pre.next = right; temp = null; } return res.next; } }

相似文章(系统自动检测得出)

  • Java集合 0.76% 庶卒 2020-11-24
  • SAAS权限管理系统| 概览 0.75% 庶卒 2020-11-11
  • ArrayList、Vector和Stack 0.40% 庶卒 2020-11-24
  • Java枚举 0.18% 庶卒 2020-11-24
  • 标签