链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储,链表在插入的时候可以达到 O(1)的复杂度,比另一种线性表 —— 顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(n) 和 O(1)。
链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
链表的节点结构ListNode已经定义好,我们发现,反转链表的过程,其实跟val没有关系,只要把每个节点的next指向之前的节点就可以了。
从代码实现上看,可以有迭代和递归两种形式。
假设存在链表 1→2→3→null,我们想要把它改成null←1←2←3。
我们只需要依次迭代节点遍历链表,在迭代过程中,将当前节点的 next 指针改为指向前一个元素就可以了。
代码如下:
public class ReverseLinkedList { public ListNode reverseList(ListNode head) { ListNode curr = head; ListNode prev = null; // 依次迭代遍历链表 while (curr != null){ ListNode tempNext = curr.next; curr.next = prev; prev = curr; curr = tempNext; } return prev; } }
复杂度分析
时间复杂度:O(n),假设 n 是链表的长度,时间复杂度是 O(n)。
空间复杂度:O(1)。
递归的核心,在于当前只考虑一个节点。剩下部分可以递归调用,直接返回一个反转好的链表,然后只要把当前节点再接上去就可以了。
假设链表为(长度为m):
n1 → n2 → …→nk−1 →nk →nk+1 →…→nm → null
若我们遍历到了nk,那么认为剩余节点nk+1到nm 已经被反转。
n1 → n2 → …→nk−1 →nk → nk+1 ←…← nm
我们现在希望 nk+1 的下一个节点指向 nk,所以,应该有
nk+1.next = nk
代码如下:
public ListNode reverseList(ListNode head) { if (head == null || head.next == null){ return head; } ListNode restHead = head.next; ListNode reversedRest = reverseList(restHead); // 递归反转 restHead.next = head; head.next = null; return reversedRest; }
复杂度分析
时间复杂度:时间复杂度:O(n),假设 n 是链表的长度,那么时间复杂度为 O(n)。
空间复杂度:O(n),由于使用递归,将会使用隐式栈空间。递归深度可能会达到 n 层。
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
链表节点结构已经定义好,而且已经做了升序排列。现在我们需要分别遍历两个链表,然后依次比较,按从小到大的顺序生成新的链表就可以了。这其实就是“归并排序”的思路。
最简单的想法,就是逐个遍历两个链表中的节点,依次比对。
我们假设原链表为list1和list2。只要它们都不为空,就取出当前它们各自的头节点就行比较。值较小的那个结点选取出来,加入到结果链表中,并将对应原链表的头(head)指向下一个结点;而值较大的那个结点则保留,接下来继续做比对。
另外,为了让代码更加简洁,我们可以引入一个哨兵节点(sentinel),它的next指向结果链表的头结点,它的值设定为-1。
代码如下:
public class MergeTwoSortedLists { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //定义一个哨兵节点 ListNode resultPrev = new ListNode(-1); ListNode prev = resultPrev; // 遍历两个链表 while ( l1 != null && l2 != null ){ if ( l1.val <= l2.val ){ prev.next = l1; prev = l1; l1 = l1.next; } else { prev.next = l2; prev = l2; l2 = l2.next; } } prev.next = (l1 == null) ? l2 : l1; return resultPrev.next; } }
复杂度分析
时间复杂度:O(n + m) ,其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。
空间复杂度:O(1)。我们只需要常数的空间存放若干变量。
用递归的方式同样可以实现上面的过程。
当两个链表都不为空时,我们需要比对当前两条链的头节点。取出较小的那个节点;而两条链其余的部分,可以递归调用,认为它们已经排好序。所以我们需要做的,就是把前面取出的那个节点,接到剩余排好序的链表头节点前。
代码如下:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if ( l1 == null ) return l2; else if ( l2 == null ) return l1; if ( l1.val <= l2.val ){ l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }
复杂度分析
时间复杂度:O(n + m),其中 nn 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。
空间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
在链表中删除某个节点,其实就是将之前一个节点next,直接指向当前节点的后一个节点,相当于“跳过”了这个节点。
当然,真正意义上的删除,还应该回收节点本身占用的空间,进行内存管理。这一点在java中我们可以不考虑,直接由JVM的GC帮我们实现。
最简单的想法是,我们首先从头节点开始对链表进行一次遍历,得到链表的长度 L。
然后,我们再从头节点开始对链表进行一次遍历,当遍历到第 L-N+1 个节点时,它就是我们需要删除的倒数第N个节点。
这样,总共做两次遍历,我们就可以得到结果。
代码如下:
public class RemoveNthNodeFromEnd { public ListNode removeNthFromEnd(ListNode head, int n) { // 遍历链表,获取长度 int l = getLength(head); // 定义哑节点(哨兵) ListNode sentinel = new ListNode(-1); sentinel.next = head; // 再次遍历,找到倒数第N个 ListNode curr = sentinel; for ( int i = 0; i < l - n; i++ ){ curr = curr.next; } curr.next = curr.next.next; return sentinel.next; } // 定义一个获取链表长度的方法 public static int getLength(ListNode head){ int length = 0; while ( head != null ){ length ++; head = head.next; } return length; } }
复杂度分析
时间复杂度:O(L),其中 L 是链表的长度。只用了两次遍历,是线性时间复杂度。
空间复杂度:O(1)。
另一个思路是利用栈数据结构。因为栈是“先进后出”的,所以我们可以在遍历链表的同时将所有节点依次入栈,然后再依次弹出。
这样,弹出栈的第 n 个节点就是需要删除的节点,并且目前栈顶的节点就是待删除节点的前驱节点。这样一来,删除操作就变得十分方便了。
代码如下:
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode sentinel = new ListNode(-1); sentinel.next = head; // 定义栈 Stack<ListNode> stack = new Stack<>(); ListNode curr = sentinel; // 遍历链表,所有节点入栈 while ( curr != null ){ stack.push(curr); curr = curr.next; } // 依次弹栈,弹出N个 for ( int i = 0; i < n; i++ ){ stack.pop(); } stack.peek().next = stack.peek().next.next; return sentinel.next; }
复杂度分析
时间复杂度:O(L),其中 L是链表的长度。我们压栈遍历了一次链表,弹栈遍历了N个节点,所以应该耗费O(L+N)时间。N <= L,所以时间复杂度依然是O(L),而且我们可以看出,遍历次数比两次要少,但依然没有达到“一次遍历”的要求。
空间复杂度:O(L),其中 L 是链表的长度。主要为栈的开销。
我们可以使用两个指针 first 和 second 同时对链表进行遍历,要求 first 比 second 超前 N 个节点。
这样,它们总是保持着N的距离,当 first 遍历到链表的末尾(null)时,second 就恰好处于第L-N+1,也就是倒数第 N 个节点了。
代码如下:
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode sentinel = new ListNode(-1); sentinel.next = head; ListNode first = sentinel, second = sentinel; for ( int i = 0; i < n + 1; i++ ){ first = first.next; } while ( first != null ){ first = first.next; second = second.next; } second.next = second.next.next; return sentinel.next; }
复杂度分析
时间复杂度:O(L),其中 L是链表的长度。这次真正实现了一次遍历。
空间复杂