链表类算法

抽象的东西，文字描述会更乱，尽量配图写代码

反转链表

反转链表，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}

实现思路

TALK IS CHEAP

class Solution {
    public static ListNode reverseList(ListNode head) {
        ListNode got = null;
        ListNode curr = head;
        // 假设数据为 1 2 3
        while (curr != null) {
            // 1.先取出next，下次遍历将处理这个节点
            ListNode next = curr.next;
            // 2.将1->null
            curr.next = got;
            // 3.将curr取出,作为下个节点的next
            got = curr;
            // 4.curr指向下个节点，准备下次遍历将其next指向got
            curr = next;
        }
        // 最后一次
        return got;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main (String[] args) {
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);

        one.next = two;
        two.next = three;

        ListNode listNode = reverseList(one);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }
}

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

实现思路

TALK IS CHEAP

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
      	// 虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && head.next != null) {
          	// 步骤二中的2要指向head了，提前把2的next拿出来给步骤三用
            ListNode temp = head.next.next;
          	// 步骤一
            cur.next = head.next;
          	// 步骤二
            head.next.next = head;
            // 步骤三
            head.next = temp;
          	// 下轮的cur节点为本轮的head节点
            cur = head;
          	// 下轮的head节点为本轮的temp
            head = temp;
        }
        return dummy.next;
    }
}

合并两条有序列表

实现思路

TALK IS CHEAP

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        }
        if (l2 != null) {
            p.next = l2;
        }
        return dummy.next;
    }
}