文章目录

• 练习题
• 219 · 在排序链表中插入一个节点
• 452 · 删除链表中的元素
• 511 · 交换链表当中两个节点
• 228 · 链表的中点
• 170 · 旋转链表
• 99 · 重排链表

练习题

219 · 在排序链表中插入一个节点

在链表中插入一个节点。

写了一个，但是爆了一个错，不知道是什么错误

def insertNode(self, head, val):
        # write your code here
        node = ListNode(val)
        res, prev = head, head
        if not head: return node
        elif not head.next:
            if head.val > val:
                node.next = head
                return node
            else: 
                head.next = node
                return head
        head = head.next
        while head:
            if head.val >= val:
                prev.next = node
                node.next = head
                break
            prev = prev.next
            head = head.next
        return res

下面是官方答案。。。。

class Solution:
    # @param head, a ListNode
    # @param val, an integer
    # @return the head of new linked list
    def insertNode(self, head, val):
        # Write your code here
        dummy = ListNode(0, head)
        p = dummy
        while p.next and p.next.val < val:
            p = p.next
        node = ListNode(val, p.next)
        p.next = node
        return dummy.next

用了p.next.val，点睛之笔。

452 · 删除链表中的元素

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

我还是不能考虑全面，还是在打补丁，这可绝对不行。

def removeElements(self, head, val):
        # write your code here
        if not head.next:
            if head.val == val: return
            else: return head

        while head and head.val == val:
            head = head.next
        if not head: return

        cur = head
        
        while cur:
            while cur.next and cur.next.val == val:
                cur.next = cur.next.next
            cur = cur.next
        return head

官方答案：

def removeElements(self, head, val):
        # write your code here
        dummy = ListNode(-1, head)
        p = dummy
        while p.next:
            if p.next.val == val:
                p.next = p.next.next
            else:
               p = p.next
        return dummy.next   

511 · 交换链表当中两个节点

给你一个链表以及两个权值v1和v2，交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同，如果没有找到对应节点，那么什么也不用做。

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    """
    @param head: a ListNode
    @param v1: An integer
    @param v2: An integer
    @return: a new head of singly-linked list
    """
    def swapNodes(self, head, v1, v2):
        # write your code here
        cur, pre = head, None
        while cur:
            if not pre and (cur.val == v1 or cur.val == v2):
                pre = cur
            if (cur.val == v1 or cur.val == v2) and cur.val != pre.val:
                pre.val, cur.val = cur.val, pre.val
                break
            cur = cur.next
        return head
           

官方答案，我觉得好复杂：

def swapNodes(self, head, v1, v2):
        if head is None:
            return None
            
        dummy = ListNode(0)
        dummy.next = head
        
        prev1, prev2 = self.findPrevs(dummy, v1, v2)
        
        if prev1 is None or prev2 is None:
            return head
            
        if prev1 == prev2:
            return head
            
        if prev1.next == prev2:
            self.swapAdjcent(prev1)
        elif prev2.next == prev1:
            self.swapAdjcent(prev2)
        else:
            self.swapRemote(prev1, prev2)
            
        return dummy.next
    
    # head->...->prev1->v1->...->prev2->v2...
    # return prev1 & prev2
    def findPrevs(self, dummy, v1, v2):
        prev1, prev2 = None, None
        
        node = dummy
        while node.next is not None:
            if node.next.val == v1:
                prev1 = node
            if node.next.val == v2:
                prev2 = node
            node = node.next
        return prev1, prev2
            
    # dummy->head->..->prev->node1->node2->post...
    # swap node1 & node2
    def swapAdjcent(self, prev):
        node1 = prev.next
        node2 = node1.next
        post = node2.next
        
        prev.next = node2
        node2.next = node1
        node1.next = post
    
    # dummy->head->..->prev1->node1->post1->...->prev2->node2->post2...
    # swap node1 & node2
    def swapRemote(self, prev1, prev2):
        node1 = prev1.next
        post1 = node1.next
        
        node2 = prev2.next
        post2 = node2.next
        
        prev1.next = node2
        node2.next = post1
        
        prev2.next = node1
        node1.next = post2

228 · 链表的中点

找链表的中点，并返回这个节点。

def middleNode(self, head):
        # write your code here
        if not head: return
        count = -1
        dummy = ListNode(0, head)
        while head:
            count += 1
            head = head.next
        head = dummy.next
        for _ in range(count // 2):
            head = head.next
        return head

一个大佬的回答，关于思考题的答案：

def middleNode(self, head):
        # write your code here
        if not head:
            return None
            
        count = 0
        middle = head
        while head.next:
            head = head.next
            count += 1
            if count % 2 == 0:
                middle = middle.next
        return middle

快慢指针的想法，快指针走2步，慢指针走1一步，当快指针走完的时候，慢指针刚好在中间。

170 · 旋转链表

给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数

class Solution:
    """
    @param head: the List
    @param k: rotate to the right k places
    @return: the list after rotation
    """
    def rotateRight(self, head, k):
        # write your code here
        if not head: return None
        fast, slow = head, head
        if not fast.next: return fast

        # 计算除loop真实步长
        cur = head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        k %= count
        if k == 0: return head

        for _ in range(k):
            fast = fast.next
            
        while fast.next:
            slow = slow.next
            fast = fast.next

        res = slow.next
        slow.next = None
        fast.next = head
        return res

官方答案，和我写的差不多：

class Solution:
    # @param head: the list
    # @param k: rotate to the right k places
    # @return: the list after rotation
    def rotateRight(self, head, k):
        # write your code here
        if head==None:
            return head
        curNode = head
        size = 1
        while curNode!=None:
            size += 1
            curNode = curNode.next
        size -= 1
        k = k%size
        if k==0:
            return head
        len = 1
        curNode = head
        while len<size-k:
            len += 1
            curNode = curNode.next
        newHead = curNode.next
        curNode.next = None
        curNode = newHead
        while curNode.next!=None:
            curNode = curNode.next
        curNode.next = head
        return newHead

99 · 重排链表

我想写一个反转链表，然后两边同时走指针，但是不知道为什么，反转链表总是益处。于是我先看下答案吧：
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

先找到中点，然后把后半段倒过来，然后前后交替合并。

def reorderList(self, head):
        # write your code here
        if None == head or None == head.next:
            return head

        pfast = head
        pslow = head
        
        while pfast.next and pfast.next.next:
            pfast = pfast.next.next
            pslow = pslow.next
        pfast = pslow.next
        pslow.next = None
        
        pnext = pfast.next
        pfast.next = None
        while pnext:
            q = pnext.next
            pnext.next = pfast
            pfast = pnext
            pnext = q

        tail = head
        while pfast:
            pnext = pfast.next
            pfast.next = tail.next
            tail.next = pfast
            tail = tail.next.next
            pfast = pnext
        return head