博客

起源

对链表而言需要用上上一个节点的操作对头结点就不适合，一个不小心产生许多bug

虚拟节点~dummy


在链表的头部放入一个哨兵，然后连上head节点，

把head节点当做普通节点

放心使用

ListNode* dummy=new ListNode(-1);
        dummy->next=head;

最后返回

 return dummy->next;

题面

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

例如，

给出的链表为:1->2->3->4->5, n= 2.

删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

上码

• 快慢指针找到被删除节点的前置节点
• 用哨兵虚拟节点，解决原生链头操作bug

func removeNthFromEnd( head *ListNode ,  n int ) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    slow,fast := dummy, dummy
    for fast != nil && fast.Next != nil{
        n--
        if n < 0 {
            slow = slow.Next
        }
        fast = fast.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}

交互链表节点

将给定的链表中每两个相邻的节点交换一次，返回链表的头指针

要求 只能使用常量级的空间。你不能修改列表中的值，只能修改节点本身。

例如, 给出1->2->3->4，返回链表2->1->4->3

解法

• 引用别名变量左值的修改会导致被引用对象的内容发生改变
• 但步骤一在别名变量被重新赋值后，即产生新的引用地址时，原先被
  
  引用链接性中断
  
  ，只对新来者负责
• 区分左值修改连动性，与左值赋值覆盖性
• 使用dummy 假面副本别名，本体不动，内部修改可追溯
• 先修改指向，占位，后移动指针，补位，赋值意味着重新来过

func swapPairs( head *ListNode ) *ListNode {
    if head == nil {
        return nil
    }
    dummy := &ListNode{Next: head}
    for prev,cur := dummy,head; cur != nil && cur.Next != nil; {
        prev.Next = cur.Next
        cur.Next = prev.Next.Next
        prev.Next.Next = cur
        
        prev = cur
        cur = cur.Next
    }
    return dummy.Next
}

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

只有不相同的情况下，当前指针才往后移动

func deleteDuplicates( head *ListNode ) *ListNode {
    dummy := &ListNode{Next: head}
    for cur :=dummy;cur!=nil && cur.Next!=nil; {
        if cur.Next.Val != cur.Val {
           cur = cur.Next
        }else{
           cur.Next = cur.Next.Next
        }
    }
    return dummy.Next
}

划分链表

给出一个链表和一个值 ，以 为参照将链表划分成两部分，使所有小于 的节点都位于大于或等于 的节点之前。

两个部分之内的节点之间要保持的原始相对顺序。

给出 1→4→3→2→5→2 和 x=3,

返回 1→2→2→4→3→5.

分析

采用

双哑节点+双指针

，先构建中间链表，然后将两个链表合并

• 哑节点指向两个中间链表的头部
• 指针指向两个中间链表的尾部

func partition( head *ListNode ,  x int ) *ListNode {
    dummy := &ListNode{}
    dummy2 := &ListNode{}
    p1,p2 := dummy,dummy2
    for cur:=head; cur!=nil;cur=cur.Next{
        if cur.Val < x {
            p1.Next = cur
            p1 = cur
        }else{
            p2.Next = cur
            p2 = cur
        }
    }
    p1.Next = dummy2.Next
    p2.Next = nil
   
    return dummy.Next
}

• 链表序本质也是一种有序，只不过是逻辑上指针有序，而非数组固定物理有序
• 若链表重置原地重生成本很高，考虑构建新的辅助链表，链表节点重建，复写