leecode-链表相关题目题目

找出两个链表的交点

力扣

题目描述

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4],skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

题目解答

1.先让两个链表走到尾部求出链表长度，再让长的那个链表先走两个链表的差值，再同时向前走直到相等节点出现。

2.假设第一个链表长度为a+c，第二个链表长度为b+c，则有a+c+b=b+c+a。即当第一个链表走到尾部时再从第二个链表头部开始，第二个链表走到尾部时再从第一个链表头部开始，此时指针就会走到交点位置。

其实两个思路一样，就是要相等同时走。

值得思考的是我用这个代码超时了:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 = headA
        l2 = headB
        while(l1 != l2):
            if l1.next is not None:
                l1 = l1.next
            else:
                l1 = headB
            if l2.next is not None:
                l2 = l2.next
            else:
                l2 = headA
        return l1

改了一下才通过

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 = headA
        l2 = headB
        # while(l1 != l2):
        #     if l1.next is not None:
        #         l1 = l1.next
        #     else:
        #         l1 = headB
        #     if l2.next is not None:
        #         l2 = l2.next
        #     else:
        #         l2 = headA
        # return l1
        while(l1 != l2):
            l1 = l1.next if l1 is not None else headB
            l2 = l2.next if l2 is not None else headA
        return l1

反转链表

力扣

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题目解答

其实可以直接用python列表的reverse

迭代：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        newhead = ListNode(None)
        while head != None:
            newnode = ListNode(head.val)
            if newhead.next is not None:
                newnode.next = newhead.next
            newhead.next = newnode
            head = head.next
        return newhead.next

递归：每次新建头节点接上当前节点。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        next = head.next
        newhead = self.reverseList(next)
        next.next = head
        head.next = None
        return newhead

合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题目解答

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l =ListNode(None)
        while l1 and l2:
            if(l1.val <= l2.val):
                l.next = ListNode(l1.val)
                l1 = l1.next
            else:
                l.next = ListNode(l2.val)
                l2 = l2.next
            l = l.next
        if l1:
            l.next = l1
        else:
            l.next = l2
        return head.next

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

题目描述

力扣

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

题目解答

迭代：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        l1 = head
        while l1 is not None:
            l2 = l1
            while l2.next is not None and l2.next.val == l2.val:
                l2.next = l2.next.next
            l1 = l1.next
        return head

递归：

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        head.next = self.deleteDuplicates(head.next)
        if head.val == head.next.val:
            return head.next
        else:
            return head

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

力扣

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

题目解答

如果用两遍扫描，可以第一遍统计链表长度。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        l1 = head
        while l1 is not None:
            length += 1
            l1 = l1.next
        if length == 1:
            return None
        if n == 1:
            l1 = head
            while l1.next.next is not None:
                l1 = l1.next
            l1.next = None
            return head
        if n == length:
            head = head.next
            return head
        length1 = length - n -1
        a = 0
        l1 = head
        while a < length1:
            l1 = l1.next
            a += 1
            print(a,l1.val)
            #print(a)
        #print(l1.val)
        l1.next = l1.next.next
        return head

如果一遍遍历：可以让一个指针先走n，再让一个指针从头开始和第一个指针同时遍历链表直到第一个指针走到链表尾部。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        l1 = l2 = head
        while n > 0:
            l1 = l1.next
            n -= 1
        if l1 is None:#删除第一个
            return head.next
        while l1.next is not None:
            l1 = l1.next
            l2 = l2.next
        l2.next = l2.next.next
        return head

两两交换链表中的节点

力扣

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题目解答

迭代：

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        newhead = ListNode(-1)
        newhead.next = head
        l1 = newhead
        while l1.next is not None and l1.next.next is not None:
            l2 = l1.next
            l1.next = l2.next
            l2.next = l2.next.next
            l1.next.next = l2
            l1 = l2

        return newhead.next

递归：

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        next = head.next
        head.next = self.swapPairs(next.next)
        next.next = head
        return next

两数相加Ⅱ

力扣

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

题目解答

如果能进行翻转就和两数相加Ⅰ一样了。

逆序处理：栈！

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        list1 = []
        list2 = []
        head = l = ListNode(None)
        while l1 is not None:
            list1.append(l1.val)
            l1 = l1.next
        while l2 is not None:
            list2.append(l2.val)
            l2 = l2.next
        jinWei = 0
        while len(list1) != 0 or len(list2) != 0 or jinWei != 0:
            if not(list1 == []):
                add1 = list1.pop()
            else:
                add1 = 0
            if not(list2 == []):
                add2 = list2.pop()
            else:
                add2 = 0
            sum = add1 + add2 + jinWei
            newNode = ListNode(sum % 10)
            if l.next is not None:
                newNode.next = l.next
            else:
                newNode.next = None
            l.next =newNode
            jinWei = sum // 10

        return head.next

回文链表

力扣

题目描述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题目解答

O(n)的方法比较简单，将链表复制到由前驱的数据结构中即可比较。

• python
• java

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # O(N)
        l1 = head
        list = []
        while l1 is not None:
            list.append(l1.val)
            l1 = l1.next
        a = 0
        b = len(list) - 1
        while a < b:
            if list[a] == list[b]:
                a += 1
                b -= 1
            else:
                break
        if a >= b:
            return True
        else:
            return False

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List <Integer> a = new ArrayList<>();
        ListNode l1 = head;
        while (l1 != null) {
            a.add(l1.val);
            l1 = l1.next;
        }
        int i = 0, j = a.size() - 1;
        while (i < j) {
            if (!a.get(i).equals(a.get(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

O(1)的解决办法是将链表拆分成两半，将第二部分翻转再一一比较。

• python
• java

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        if fast is not None:
            slow = slow.next
        newhead = slow
        newhead = self.reverse(newhead)
        while head is not None and newhead is not None:
            if head.val != newhead.val:
                return False
            head = head.next
            newhead = newhead.next
        return True

    def reverse(self, head):
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

public class palindrome_linked_list {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        ListNode newHead = reverse(slow);
        while (newHead != null && head != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;

        }

    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }

}

分割链表

力扣

题目描述

定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

提示:

• root 的长度范围： [0, 1000].
• 输入的每个节点的大小范围：[0, 999].
• k 的取值范围： [1, 50].

题目解答

思路是计算平均长度和余数，若余数是n就在数组前n个链表增加一个长度。

举例：

11 / 3 = 3 余 2： 一共有3段，每段平均3个节点，剩下了2个节点
根据题意长的链表排前面，短的链表排后面，所以只有前面的两个子链表一个多一个多余的节点，便形成了 4 4 3 的结构。

• python
• java

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        l = root
        length = 0
        listNodeList = []
        while l is not None:
            length += 1
            l = l.next
        aveLength = length // k
        remainder = length % k
        print(aveLength, remainder)
        l = root
        while k > 0:
            #tempListNode = []
            tempLength = aveLength
            if remainder > 0:
                tempLength += 1
            l1 = head = l
            pre = ListNode(None)
            while tempLength > 0:
                pre = l1
                l1 = l1.next
                tempLength -= 1
            l = l1
            pre.next = None
            listNodeList.append(head)
            k -= 1
            remainder -= 1
        return listNodeList

public ListNode[] splitListToParts(ListNode root, int k) {
    int N = 0;
    ListNode cur = root;
    while (cur != null) {
        N++;
        cur = cur.next;
    }
    int mod = N % k;
    int size = N / k;
    ListNode[] ret = new ListNode[k];
    cur = root;
    for (int i = 0; cur != null && i < k; i++) {
        ret[i] = cur;
        int curSize = size + (mod-- > 0 ? 1 : 0);
        for (int j = 0; j < curSize - 1; j++) {
            cur = cur.next;
        }
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    return ret;
}

奇偶链表

力扣地址

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

题目解答

比较简单，设置奇数节点头为head，偶数节点头为head.next分别将奇数位和偶数位接上，最后将偶数节点头接到奇数节点的尾。

• python
• java

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        odd, even = head, head.next
        evenHead = even
        while even is not None and even.next is not None:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
        odd.next = evenHead
        return head

public ListNode oddEvenList(ListNode head) {
    if (head == null) {
        return head;
    }
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = odd.next.next;
        odd = odd.next;
        even.next = even.next.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

环形链表

力扣地址

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

题目解答

双指针，快慢指针，若有环，必不能等于null。

• python
• java

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        if head.next is None:
            return False
        low,fast = head,head.next
        while fast is not None and low is not None and fast.next is not None:
            if fast == low:
                return True
            else:
                fast = fast.next.next
                low = low.next
        return False

/**
 * 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) {
         if(head == null || head.next == null)
          return false;
        ListNode fast = head.next;
       ListNode slow = head;
        while(slow != null && fast != null)
        {
            if(fast == slow)
                return true;
            slow = slow.next;
            if(fast.next != null)
                fast = fast.next.next;
            else
                return false;
        }
        return false;
    }
}

感叹一下，java真快啊。。