Dummy Node

值得思考的实现

链表Dummy Node

(一)Partition List

https://leetcode.com/problems/partition-list/description/

题目:给出一个链表和一个x值,要求返回一个顺序链表使得小于x的数在链表前面,大于等于x的数在链表后面,保证节点顺序不变。

      例如:$1->3->2->4->2, 3$ 变成:$1->2->2->3->4$
解答:建立两个新的左、右指针及dummy node,使用head指针遍历整个链表,遇到大于等于head的节点则放到右链表,否则放到左链表。最后将左右链表相连。 第一次犯错:忘记将又指针的尾部指向null;

代码:

class Solution {
    public ListNode partition(ListNode head, int x) {
         if (head == null) {
            return head;
        }
        
        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode left = leftDummy;
        ListNode right = rightDummy;
        
        while (head != null) {
            if (head.val >= x) {
                right.next = head;
                right = right.next;
            } else {
                left.next = head;
                left = left.next;
            }
            head = head.next;
        }
        right.next = null;
        left.next = rightDummy.next;
        return leftDummy.next;
    }
}

(二) Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/

AC!

题目:将两个顺序链表合并成一个顺序链表;

解答:依次比较两个链表里的值大小进行排列;

改进:当一个链表指针指向null,另一个链表还没时,可以直接将重新排列的链表尾指向当前指针:


           if (l1 != null) {

           head.next = l1;

           } else {

           head.next = l2;

          }

代码:


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

(三)swap two nodes in linked list

https://leetcode.com/problems/swap-nodes-in-pairs/description/

AC!

题目:两两交换链表中节点位置。如:$1->2->4->5->6$ 转变为: $2->1->5->4->6$

解答:使用两个指针遍历链表;

代码:

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode headNext = head.next;
        ListNode headPrev = dummy;
        
        while (head != null && headNext != null) {
            headPrev.next = headNext;
            head.next = headNext.next;
            headNext.next = head;
            headPrev = head;
            head = head.next;
            if (head != null) {
                headNext = head.next;
            }
        }
        return dummy.next;
    }
}

(四)reorder list

https://leetcode.com/problems/reorder-list/description/

题目:给定一个单链表:$L0->L1->…->Ln-1->Ln,$

      重新排序后为:$L0->Ln->L1->Ln-1->L2->Ln-2->...$
解答: 第一次犯错:将链表尾连接到头之后,忘记将尾的前一个指针指向空; 第二次犯错:忘记考虑链表头和prevTail重合的情况(偶数链表)。

代码:

class Solution {
    public void reorderList(ListNode head) {
        while (head != null && head.next != null) {
            ListNode prevTail = head;
            while (prevTail.next.next != null) {
                prevTail = prevTail.next;
            }
            ListNode tail = prevTail.next;
            if (head.next == tail) {
                break;
            } 
            tail.next = head.next;
            head.next = tail;
            head = head.next.next;
            prevTail.next = null;
        }
    }
}

(四)Rotate List

https://leetcode.com/problems/rotate-list/description/

题目:将链表尾部的k个节点移到链表头部;

解答:每次将链表最后一个节点移动至链表头,移动k次;

第一次犯错:(超时)先遍历链表,得到链表长度length,循环只需执行 k%length 次;

代码:

class Solution {
    public ListNode rotateRight(ListNode head, int k) {


        ListNode tail = head;
        int length = 0;
        
        while (tail != null ) {
            length++;
            tail = tail.next;
        }
        
        if (length == 0 || length == 1) {
            return head;
        }
        
        for (int i = 0; i < k % length; i++) {
            ListNode preTail = head;
            while (preTail != null && preTail.next != null && preTail.next.next != null) {
                preTail = preTail.next;
            }
            tail = preTail.next;
            tail.next = head;
            preTail.next = null;
            head = tail;
        }
        return head;
    }
}


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!