合并兩個排序的鏈表&反轉(zhuǎn)鏈表&兩兩交換鏈表中的節(jié)點

合并兩個排序的鏈表

輸入兩個遞增排序的鏈表可霎，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的咏花。

示例1：

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

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

        }
        r=r.next;
    }
    r.next=l1==null?l2:l1;
    return dummy.next;
}

遞歸形式：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1==null){
        return l2;
    }
    if(l2==null){
        return l1;
    }
    ListNode head;
    if(l1.val<=l2.val){
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    } else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    }
}

反轉(zhuǎn)鏈表

方法一：迭代

public ListNode reverseList(ListNode head) {
    ListNode newHead=null;
    ListNode p=head;
    while(p!=null){
        ListNode next=p.next;
        p.next=newHead;
        newHead=p;
        p=next;
    }
    return newHead;
}

方法二：遞歸

public ListNode reverseList(ListNode head) {
    if(head==null||head.next==null){
        return head;
    }
    ListNode p=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return p;
}

反轉(zhuǎn)鏈表 II

反轉(zhuǎn)從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉(zhuǎn)短蜕。

說明:
1 ≤ m ≤ n ≤ 鏈表長度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

方法一：迭代

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy=new ListNode(0);//m=1時
    dummy.next=head;
    ListNode p = dummy;//指向開始反轉(zhuǎn)位置的前一個元素
    ListNode nextP = dummy.next;//指向開始反轉(zhuǎn)位置傻咖，即反轉(zhuǎn)后的鏈尾
    for (int i = 0; i < m-1 ; i++) {
        p = p.next;
        nextP = nextP.next;
    }
    ListNode[] ans = reverseList(nextP, n - m + 1);
    p.next = ans[0];
    nextP.next = ans[1];
    return dummy.next;
}

public ListNode[] reverseList(ListNode head, int n) {
    ListNode newHead = null;
    ListNode p = head;
    ListNode[] ans = new ListNode[2];

    ListNode next =null;
    for (int i = 0; i < n; i++) {
        next = p.next;
        p.next = newHead;
        newHead = p;
        p = next;
    }
    ans[0] = newHead;//新的頭結(jié)點
    ans[1] = next;//反轉(zhuǎn)前鏈表尾的后一個元素
    return ans;
}

方法二：遞歸

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==1){//從第一個位置開始朋魔，即返回前n個
        return reverseList(head,n);
    }
    head.next=reverseBetween(head.next,m-1,n-1);
    return head;
}

private ListNode successor;

//反轉(zhuǎn)前n個元素
public ListNode reverseList(ListNode head, int n) {
    if(n==1){
        successor=head.next;//記錄后繼結(jié)點
        return head;
    }
    ListNode p=reverseList(head.next,n-1);
    head.next.next=head;
    head.next=successor;//將head指向后繼，反轉(zhuǎn)整條鏈表尾null
    return p;
}

K 個一組翻轉(zhuǎn)鏈表

給你一個鏈表卿操，每 k 個節(jié)點一組進行翻轉(zhuǎn)铺厨，請你返回翻轉(zhuǎn)后的鏈表。

k 是一個正整數(shù)硬纤，它的值小于或等于鏈表的長度解滓。

如果節(jié)點總數(shù)不是 k 的整數(shù)倍，那么請將最后剩余的節(jié)點保持原有順序筝家。

示例：

給你這個鏈表：1->2->3->4->5

當 k = 2 時洼裤，應(yīng)當返回: 2->1->4->3->5

當 k = 3 時，應(yīng)當返回: 3->2->1->4->5

思路：回憶常規(guī)鏈表反轉(zhuǎn)溪王，將每部分反轉(zhuǎn)的鏈起來

//常規(guī)鏈表反轉(zhuǎn)
public static ListNode reverse(ListNode head,int k) {
    ListNode p=head;
    ListNode newHead=null;
    for (int i = 0; i <k ; i++) {
        ListNode next=p.next;
        p.next=newHead;
        newHead=p;
        p=next;
    }
    return newHead;
}

public static ListNode reverseKGroup(ListNode head, int k) {
    //參考上一題利用啞結(jié)點
    ListNode dummy=new ListNode(0);
    dummy.next=head;
    //用于鏈接鏈表
    ListNode p=dummy;
    //用于判斷剩余結(jié)點是否是k的整數(shù)倍
    ListNode q=head;
    //臨時保存應(yīng)該常規(guī)反轉(zhuǎn)鏈表的開始位置
    ListNode temp;
    while (p!=null){
        temp=q;
        for (int i = 0; i < k; i++) {
            //不夠直接鏈接
            if(q==null){
                p.next=temp;
                return dummy.next;
            }
            q=q.next;
        }
        p.next= reverse(temp, k);
        p=temp;
    }
    return dummy.next;
}

對于這個鏈表：1->2->3->4->5

添加啞結(jié)點后: 0->1->2->3->4->5 此時p=0 q=1

第一次反轉(zhuǎn)

temp=1 q=3 2= reverse(1,2)

0->2->1 p=1 剩下3->4>5

第二次反轉(zhuǎn)

temp=3 q=5 4=reverse(3,2)

0->2->1->4->3 p=3 剩下 5

第三次

temp=5 q==null 0->2->1->4->3->5

新代碼

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode p = head;
    ListNode linkNode = dummy;//用于連接鏈表
    while (p != null) {
        ListNode seeNode = p;//向前查看是否有k個
        for (int i = 0; i < k; i++) {
            if (seeNode == null) {//不夠了直接順序返回
                linkNode.next = p;
                return dummy.next;
            }
            seeNode = seeNode.next;
        }
        ListNode[] reverseNode = reverse(p, k);
        linkNode.next = reverseNode[0];//連接到反轉(zhuǎn)后的頭結(jié)點
        linkNode = p;//反轉(zhuǎn)前的頭結(jié)點成了尾結(jié)點腮鞍，現(xiàn)在連接從這里開始
        p = reverseNode[1];
    }
    return dummy.next;
}

// 返回新的頭結(jié)點和原來鏈表n+1位置的結(jié)點
public ListNode[] reverse(ListNode head, int n) {
    ListNode newHead = null;
    ListNode p = head;
    for (int i = 0; i < n; i++) {
        ListNode next = p.next;
        p.next = newHead;
        newHead = p;
        p = next;
    }
    return new ListNode[]{newHead, p};
}

兩兩交換鏈表中的節(jié)點

給定一個鏈表，兩兩交換其中相鄰的節(jié)點莹菱，并返回交換后的鏈表移国。

你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換道伟。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

鏈表中節(jié)點的數(shù)目在范圍 [0, 100] 內(nèi)
0 <= Node.val <= 100

方法一：迭代

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode p = head;
    ListNode link = dummy;
    while (p != null && p.next != null) {
        ListNode pair = p.next;
        ListNode next = pair.next;
        pair.next = p;
        link.next = pair;
        link = p;
        p.next = next;
        p = next;
    }
    return dummy.next;
}

方法二：遞歸

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode nextHead = swapPairs(head.next.next);
    ListNode next = head.next;
    next.next = head;
    head.next = nextHead;
    return next;
}