Parity linked list [two general directions of linked list operation]

Preface

There are two ways to operate a linked list , One is simple operation , Just operate on the linked list ; One is very nice All-round operation , Set up dummy node , Can unify the empty linked list / The first node operates , Insert the nodes that meet the conditions with the header / Tail insertion dummy after .

One 、 Two general directions of linked list operation

Two 、dummy

package everyday.listNode;

//  Odd and even list 
public class OddEvenList {
    
    /* target： Odd before even , Put even numbers first , Odd numbers come back .  There are two ways to operate a linked list , One is simple operation , Just operate on the linked list ;  One is very nice All-round operation , Set up dummy node , Can unify the empty linked list / The first node operates , Insert the nodes that meet the conditions with the header / Tail insertion dummy after . */
    public ListNode oddEvenList(ListNode head) {
    
        int cnt = 1;//  Odd before even / First and then odd , Put the same kind of sequential tail interpolation together .
        ListNode dummy1 = new ListNode();
        ListNode p1 = dummy1;
        ListNode dummy2 = new ListNode();
        ListNode p2 = dummy2;
        //  Get parity linked list .
        while (head != null) {
    
            //  Get the processed node .
            ListNode node = head;
            head = head.next;//  Go to the next node first , OK, clean up the last node .
            node.next = null;
            if ((cnt & 1) == 1) {
    
                p1.next = node;
                p1 = p1.next;
            }
            if ((cnt & 1) == 0) {
    
                p2.next = node;
                p2 = p2.next;
            }
            //  Identifies the next parity .
            cnt = ++cnt & 1;
        }
        //  Connect the two linked lists .
        p1.next = dummy2.next;
        return dummy1.next;
    }

    // Definition for singly-linked list.
    public class ListNode {
    
        int val;
        ListNode next;

        ListNode() {
    
        }

        ListNode(int val) {
    
            this.val = val;
        }

        ListNode(int val, ListNode next) {
    
            this.val = val;
            this.next = next;
        }
    }

}

summary

1） There are two ways to operate a linked list , General recommendation dummy Law . If it is a very simple linked list operation , You can also directly operate the linked list in place .

reference

[1] LeetCode Two general directions of linked list operation