算法 之 链表

大概说明

链表操作，一般两种方式保存结果，一是新建node作为结果，二是创建dummy虚拟节点，通过temp.next的赋值，修改dummy的链表，然后通过dummy.next返回结果。

学习中，记录备份一下~

节点结构

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

操作说明

node1 = node2.next; // 表示node1这个变量的转变
 
node1.next= node2; // 表示node1代表的链表都更改了这个节点的next

两两交换链表节点

// 方法1 直接迭代
public ListNode swapPairs1(ListNode head) {
        ListNode dummyHead = new ListNode(0);// 设置dummy节点，方便定位最后的答案,dummy自身值不重要
        dummyHead.next = head;// 塞初始答案
        ListNode temp = dummyHead;// 临时节点，用于node交换过程中保存正确的答案
        while (temp.next != null && temp.next.next != null) {// temp.next和temp.next.next之间交换
            ListNode node1 = temp.next;// 第一个需要交换的node1
            ListNode node2 = temp.next.next;// 第二个需要交换的node2
            temp.next = node2;// 交换第一步：node2变第一个
            node1.next = node2.next;// 交换第二步：node1 接上 node2.next
            node2.next = node1;// 交换第三步：node2 next 指向 node1
            temp = node1;// 准备下次循环 temp等于下次交换的上一个，也就是node1
        }
        return dummyHead.next;// 返回定位节点dummy的next
    }
 
// 方法1 递归
public ListNode swapPairs2(ListNode head) {
        if(head == null || head.next == null) return head;// 两两交换 其中一个为空则直接返回
        ListNode newHead = head.next;// 新建head ，等于入参的next
        head.next = swapPairs2(newHead.next);// head的next 等于 下次交换的返回值
        newHead.next = head;// newHead的next等于 刚刚拿到答案的head
        return newHead;
    }